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 language | English |
---|---|
Article number | 18 |
Number of pages | 31 |
Journal | Journal of the ACM |
Volume | 66 |
Issue number | 3 |
Early online date | 12 Apr 2019 |
DOIs | |
Publication status | Published - 1 Jun 2019 |
Fingerprint Dive into the research topics of 'Uniform Sampling Through the Lovasz Locál Lemma'. Together they form a unique fingerprint.
Profiles
-
Heng Guo
- School of Informatics - Lecturer in Algorithms and Complexity
- Laboratory for Foundations of Computer Science - Lecturer in Algorithms and Complexity
- Foundations of Computation
Person: Academic: Research Active (Teaching)