Lecture Title: A Survey of the Distributed Lovasz Local Lemma Problem
Presented By: Seth Pettie, University of Michigan
Location: Rosebrugh Building, 164 College Street, Room 208
Abstract: The Lovasz Local Lemma is a well known tool to prove the existence of combinatorial objects (such as graph colorings or packet-routing schedules) and constructive (i.e., algorithmic) versions of the LLL can be applied to efficiently find those objects.
In this talk I will define the Distributed LLL problem and survey its role in distributed algorithm design, and in efforts to build a complexity theory for the LOCAL model. In short, the (randomized) Distributed LLL is sublogarithmic-time complete, and the (deterministic) Distributed LLL is PSLOCAL-complete, a class which captures what is likely to be computable deterministically in polylog n time. The Distributed LLL is known to be exponentiallyeasier to solve with randomness than without. It is also an indispensable primitive in numerous distributed algorithms, e.g., those for edge-coloring.