Return to Colloquia & Seminar listing
Uniform Sampling through the Lovász Local Lemma
ProbabilitySpeaker: | Jingcheng Liu, UC Berkeley |
Related Webpage: | https://liuexp.github.io/ |
Location: | 2112 MSB |
Start time: | Wed, Sep 26 2018, 3:10PM |
Abstract: 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 (perhaps surprising) new connections between the variable framework of the Lovász 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.
Joint work with Heng Guo and Mark Jerrum.