Name
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 clas- sical sampling algorithms such as the “cycle-popping” algorithm for rooted spanning trees by Wilson. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3055399.3055410 | STOC |
Keywords | DocType | Volume |
Exact sampling,Lovasz Local Lemma,#SAT | Conference | abs/1611.01647 |
ISSN | Citations | PageRank |
0737-8017 | 2 | 0.38 |
References | Authors | |
21 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Heng Guo | 1 | 85 | 12.02 |
| mark jerrum | 2 | 2755 | 564.62 |
| Jingcheng Liu | 3 | 27 | 3.24 |