Computer Science/Discrete Mathematics Seminar II | |

Topic: | Algorithmic proof of the Lovasz Local Lemma via resampling oracles |

Speaker: | Jan Vondrák |

Affiliation: | IBM Almaden Research Center; Member, School of Mathematics |

Date: | Tuesday, October 27 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2015/1027-Vondr%C3%A1k |

For a collection of events on a probability space with specified dependencies, the Lovasz Local Lemma ("LLL") gives a sufficient condition for the existence of a point avoiding all the events. Following Moser's discovery of an efficient algorithm for many applications of the Lovasz Local Lemma, there has been extensive research on various extensions of this result. We present a unifying algorithmic proof of the Lovasz Local Lemma (and its stronger variants such as Shearer's Lemma), independent of the underlying probability space. As a consequence, we obtain efficient algorithms for the known settings where the LLL applies (independent random variables, random permutations, perfect matchings, spanning trees). We present some new applications, in particular a new result on packings of rainbow spanning trees.