| dc.contributor.author | JERRUM, MR | |
| dc.contributor.author | GUO, H | |
| dc.contributor.author | LIU, J | |
| dc.date.accessioned | 2019-04-10T10:05:09Z | |
| dc.date.available | 2019-01-28 | |
| dc.date.available | 2019-04-10T10:05:09Z | |
| dc.date.issued | 2019 | |
| dc.identifier.issn | 0004-5411 | |
| dc.identifier.uri | https://qmro.qmul.ac.uk/xmlui/handle/123456789/56791 | |
| dc.description.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. | en_US |
| dc.publisher | Association for Computing Machinery | en_US |
| dc.relation.ispartof | Journal of the Association for Computing Machinery (ACM) | |
| dc.rights | This is a pre-copyedited, author-produced version of an article accepted for publication in https://dl.acm.org/citation.cfm?id=3055410 following peer review. The version of record is available https://dl.acm.org/citation.cfm?id=3055410 | |
| dc.title | Uniform Sampling through the Lovász Local Lemma | en_US |
| dc.type | Article | en_US |
| dc.rights.holder | Copyright © 2019 ACM, Inc. | |
| pubs.notes | Not known | en_US |
| pubs.publication-status | Accepted | en_US |
| dcterms.dateAccepted | 2019-01-28 | |
| rioxxterms.funder | Default funder | en_US |
| rioxxterms.identifier.project | Default project | en_US |
