Spring 2016

Uniform Sampling through the Lovász Local Lemma

Tuesday, Jun. 6, 2017 11:00 am12:00 pm

Add to Calendar

We propose a new algorithmic framework, called "partial rejection sampling", to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds new connections between the variable framework of the Lov\'asz Local Lemma and some classical sampling algorithms such as the "cycle-popping" algorithm for rooted spanning trees by Wilson. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences. 
Based on joint work with Mark Jerrum and Jingcheng Liu.