N&O Seminar: David Harris (University of Maryland)
- https://www.cwi.nl/research/groups/networks-and-optimization/events/n-o-seminar-david-harris-university-of-maryland
- N&O Seminar: David Harris (University of Maryland)
- 2018-12-04T11:00:00+01:00
- 2018-12-04T12:00:00+01:00
- Oblivious resampling oracles and parallel algorithms for the Lopsided Lovasz Local Lemma
- What Networks & Optimization English
- When 04-12-2018 from 11:00 to 12:00 (Europe/Amsterdam / UTC100)
- Where L016
- Contact Name Daniel Dadush
- Web Visit external website
- Add event to calendar iCal
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.