Home // SnT // News & E... // SRM Research Seminar: Variable-Version Lovász Local Lemma: Beyond Shearer's Bound

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

twitter linkedin facebook google+ email this page
Add to calendar
Speaker: Dr. Yuyi Wang (ETH Zurich)
Event date: Friday, 15 December 2017, 10:30 - 11:30
Place: Room MSA 4.140, Maison du Savoir
2, avenue de l'Université
L-4365 Esch-sur-Alzette

A tight criterion under which the abstract version Lovász 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 event-variable 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.

Dr. Yuyi Wang is a postdoc researcher in the Department of Information Technology and Electrical Engineering at ETH Zurich. Before joining ETH, he got his PhD in 2015 from KU Leuven, Belgium. During the 2015-2016 academic year he was a visiting scholar at the Institute of Computing Technology, CAS, Beijing. His research mainly focuses on topics of theoretical computer science such as Lovasz Local Lemma, online algorithms and distributed algorithms, and machine learning, in particular computational/statistical learning theory.

The SRM seminars are the joint seminars of the SATOSS and APSIA groups supported by LACS and SnT.