Uniform Sampling through the Lovász Local Lemma
View/ Open
Publisher
Journal
Journal of the Association for Computing Machinery (ACM)
ISSN
0004-5411
Metadata
Show full item recordAbstract
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.
Authors
JERRUM, MR; GUO, H; LIU, JCollections
- Mathematics [1478]