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 to 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_0, B_1 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 perfect matchings on the complete s-uniform hypergraph K_n^{(s)}, and the first commutative resampling oracle for hamiltonian cycles of K_n.
