Oblivious resampling oracles and parallel algorithms for the Lopsided Lovasz Local Lemma

摘要

The Lovasz Local Lemma (LLL) is a probabilistic tool which shows that, if a collection of "bad" events B in a probability space are not too likely and not too interdependent, then there is a positive probability that no bad-events in B occur. Moser & Tardos (2010) gave sequential and parallel algorithms which transformed most applications of the variable-assignment LLL into efficient algorithms. A framework of Harvey & Vondrak (2015) based on "resampling oracles" extended this give very general sequential algorithms for other probability spaces satisfying the Lopsided Lovasz Local Lemma (LLLL). We describe a new structural property of resampling oracles which holds for all 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 on the precise state within B itself. This property has two major consequences. First, it is the key to achieving a unified parallel LLLL algorithm, which is faster than previous, problem-specific algorithms of Harris (2016) for the variable-assignment LLLL algorithm and of Harris & Srinivasan (2014) for permutations. This new algorithm extends a framework of Kolmogorov (2016), and 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 out of a relatively simple "atomic" set of events. It was intuitively clear that existing LLLL spaces were built in this way; but the obliviousness property formalizes this and gives a way of automatically turning a resampling oracle for atomic events into a resampling oracle for conjunctions of them. Using this framework, we get the first sequential resampling oracle for rainbow pcrfcct matchings on the complete s-uniform hypergraph K_n~((s)), and the first commutative resampling oracle for hamiltonian cycles of K_n.