Oblivious Resampling Oracles and Parallel Algorithms for the Lopsided Lovasz Local Lemma

The Lovasz Local Lemma (LLL) shows that, for a collection of bad events B in a probability space that are not too likely and not too interdependent, there is a positive probability that no events in B occur. Moser and Tardos (2010) gave sequential and parallel algorithms that transformed most applications of the variable-assignment LLL into efficient algorithms. A framework of Harvey and Vondrak (2015) based on resampling oracles extended this to sequential algorithms for other probability spaces satisfying a generalization of the LLL known as the Lopsided Lovasz Local Lemma (LLLL). We describe a new structural property that holds for most known resampling oracles, which we call obliviousness. Essentially, it means that the interaction between two bad-events B, B' depends only on the randomness used to resample B and not the precise state within B itself. This property has two major consequences. First, combined with a framework of Kolmogorov (2016), it leads to a unified parallel LLLL algorithm, which is faster than previous, problem-specific algorithms of Harris (2016) for the variable-assignment LLLL and of I Iarris and Srinivasan (2014) for permutations. This gives the first RNC algorithms for rainbow perfect matchings and rainbow Hamiltonian cycles of K-n. Second, this property allows us to build LLLL probability spaces from simpler atomic events. This gives the first resampling oracle for rainbow perfect matchings on the complete s-uniform hypergraph k(n)((s)) and the first commutative resampling oracle for Hamiltonian cycles of K-n.

Automated summary

The Lovasz Local Lemma (LLL) states that it is possible for a collection of unlikely and relatively independent bad events to not occur simultaneously in a probability space. Moser and Tardos (2010) introduced algorithms that efficiently transform applications of the LLL. A framework by Harvey and Vondrak (2015) extended this to other probability spaces by using resampling oracles, leading to sequential algorithms based on a generalization of the LLL known as the Lopsided Lovasz Local Lemma (LLLL).