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.
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 language | English |
---|---|
Title of host publication | Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 |
Publisher | ACM |
Pages | 342-355 |
Number of pages | 14 |
DOIs | |
Publication status | Published - 23 Jun 2017 |
Event | STOC 2017 Theory Fest: 49th Annual ACM Symposium on the Theory of Computing - Montreal, Canada Duration: 19 Jun 2017 → 23 Jun 2017 http://acm-stoc.org/stoc2017/ |
Conference
Conference | STOC 2017 Theory Fest: 49th Annual ACM Symposium on the Theory of Computing |
---|---|
Country/Territory | Canada |
City | Montreal |
Period | 19/06/17 → 23/06/17 |
Internet address |