IDA Seminar - Variable-Version Lovász Local Lemma: Beyond Shearer's Bound

Variable-Version Lovász Local Lemma: Beyond Shearer's Bound

A tight criterion under which the abstract version Lovasz Local Lemma (abstract-LLL) holds was given by Shearer decades ago. However, little is known about that of the variable version LLL (variable-LLL) where events are generated by independent random variables, though this model of events is applicable to almost all applications of LLL. We introduce a necessary and sufficient criterion for variable-LLL, in terms of the probabilities of the events and the eventvariable graph specifying the dependency among the events. Based on this new criterion, we obtain boundaries for two families of event-variable graphs, namely, cyclic and treelike bigraphs. These are the first two non-trivial cases where the variable-LLL boundary is fully determined.

As a byproduct, we also provide a universal constructive method to find a set of events whose union has the maximum probability, given the probability vector and the event-variable graph. Though it is #P-hard in general to determine variable-LLL boundaries, we can to some extent decide whether a gap exists between a variable-LLL boundary and the corresponding abstract-LLL boundary. In particular, we show that the gap existence can be decided without solving Shearer's conditions or checking our variable-LLL criterion. Equipped with this powerful theorem, we show that there is no gap if the base graph of the event-variable graph is a tree, while gap appears if the base graph has an induced cycle of length at least 4. The problem is almost completely solved except when the base graph has only 3-cliques, in which case we also get partial solutions. A set of reduction rules are established that facilitate to infer gap existence of an event-variable graph from known ones. As an application, various event-variable graphs, in particular combinatorial ones, are shown to be gapful/gapless.

March 7, 2019 (Thursday)
Room 205, Building E, Karlovo nám. 13


Lecturer: YUYI WANG

Yuyi Wang received his B.E. degree from School of Software, Huazhong University of Science and Technology, China in June 2009, his M.S. degree from School of Computing, National University of Singapore in August 2010, and his Ph.D. degree from KULeuven, Belgium in July 2015. Now he is a Postdoc researcher at ETH Zurich. His research interest includes theoretical computer science (distributed computing, online algorithms and probabilistic methods, etc.) and artificial intelligence (statistical machine learning and graph mining, etc.).