Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Following the breakthrough discovery by Moser-Tardos of an efficient algorithm for applications of the Lovasz Local Lemma, there has been extensive research in recent years on various extensions of this result. The Moser-Tardos result assumes a product structure of the underlying probability space. Known extensions involve either new types of probability spaces (e.g. permutations) or stronger variants of the lemma (cluster expansion, Shearer's Lemma). However, a unifying algorithmic proof of the LLL independent of the underlying probability space was not known. We prove an algorithmic local lemma (in Shearer's strong form) in an abstract setting assuming a "resampling oracle" for each event. We show that the existence of resampling oracles is equivalent to a positive association property, similar to the assumption of a generalization known as the "lopsided local lemma". In particular, efficient resample oracles can be designed for the known applications settings of the lopsided local lemma (random permutations, matchings, spanning trees). We present several new algorithmic results in these scenarios. (Joint work with Nick Harvey.)