Seth Pettie
Title: A Survey of the Distributed Lovasz Local Lemma Problem.
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 algorithmic versions of the LLL can be applied to find those objects
efficiently.
In this talk I will define the Distributed LLL problem and survey its role in
the design of distributed algorithms 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 exponentially easier to solve with randomness than without.
It is also an indispensable primitive in numerous distributed algorithms,
e.g., those for edge-coloring.