Uniform sampling through the Lovasz local lemma

Heng Guo, Mark Jerrum, Jingcheng Liu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 [32]. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences.
Original languageEnglish
Title of host publicationProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017
PublisherACM
Pages342-355
Number of pages14
DOIs
Publication statusPublished - 23 Jun 2017
EventSTOC 2017 Theory Fest: 49th Annual ACM Symposium on the Theory of Computing - Montreal, Canada
Duration: 19 Jun 201723 Jun 2017
http://acm-stoc.org/stoc2017/

Conference

ConferenceSTOC 2017 Theory Fest: 49th Annual ACM Symposium on the Theory of Computing
CountryCanada
CityMontreal
Period19/06/1723/06/17
Internet address

Fingerprint Dive into the research topics of 'Uniform sampling through the Lovasz local lemma'. Together they form a unique fingerprint.

Cite this