Uniform Sampling Through the Lovasz Locál Lemma

Heng Guo, Mark Jerrum, Jingcheng Liu

Research output: Contribution to journalArticlepeer-review

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 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. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences.
Original languageEnglish
Article number18
Number of pages31
JournalJournal of the ACM
Volume66
Issue number3
Early online date12 Apr 2019
DOIs
Publication statusPublished - 1 Jun 2019

Fingerprint Dive into the research topics of 'Uniform Sampling Through the Lovasz Locál Lemma'. Together they form a unique fingerprint.

Cite this