CS Colloquium: Seth Pettie (UMICH)
The Distributed Lovasz Local Lemma
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 efficiently find those objects. The LLL and its variants are fairly well understood in the usual model of sequential computation.
In this talk I will define the Distributed LLL problem and survey its role in distributed computing. In short, the Distributed LLL problem is a useful prism to view many recent developments in the LOCAL model, such as graph shattering and the role of randomness, modern derandomization techniques, and the existence of complexity gaps in the LOCAL time hierarchy.
Bio: Seth Pettie is a Professor of Electrical Engineering and Computer Science at the University of Michigan. He received his Ph.D. from the University of Texas at Austin in 2003 and was a researcher at the Max Planck Institute for Computer Science, from 2003-2006. He grew up within a short walk of Georgetown University.
Friday, January 18, 2019 at 11:00am