***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: David Harris (U Maryland)

Thursday 28th March, 3:00 in Fine Hall 224.

Title: 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 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, 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 perfect matchings on the 
complete s-uniform hypergraph, and the first commutative resampling 
oracle for hamiltonian cycles of K_n.

		----------------------------------

Next week: Daniel Reichman

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)