*************************************************************************

                Department of Mathematical Sciences                       
                   The Johns Hopkins University                           
                                                                        
                              SEMINAR                                
                                                                        
*************************************************************************

Christian Scheideler                              March 1, 2001
Department of Computer Science                    304 Whitehead Hall
The Johns Hopkins University                      Preseminar: 3:00 p.m.
                                                  Refreshments: 3:30 p.m.
                                                  Seminar: 4:00 p.m.

*************************************************************************

  COLORING NON-UNIFORM HYPERGRAPHS: A FIRST ALGORITHMIC APPROACH 
                 TO THE GENERAL LOVASZ LOCAL LEMMA

*************************************************************************

                             ABSTRACT

The Lovasz Local Lemma is a sieve method to prove the existence of
structures with certain prescribed properties.  In most of its applications,
the Lovasz Local Lemma does not supply a polynomial-time algorithm
for finding these structures.  Beck was the first who gave a method of
converting some of these existence proofs into efficient algorithms.
He applied his technique to the symmetric form of the Lovasz Local
Lemma and, in particular, to the problem of 2-coloring uniform
hypergraphs.

My talk will concentrate on the general form of the Lovasz Local Lemma.
In particular, I will describe a randomized algorithm for 2-coloring
non-uniform hypergraphs that runs in expected linear time.
Even for uniform hypergraphs no algorithm with such a runtime bound
was previously known, and no polynomial-time algorithm was known
at all for the class of non-uniform hypergraphs I will consider.

*************************************************************************