UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Uniform Sampling through the Lovász Local Lemma

Mathematical Physics & Probability

Speaker: 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.