Uniform sampling through the Lovasz local lemma

Heng Guo; Mark Jerrum; Jingcheng Liu

doi:10.1145/3055399.3055410

Uniform sampling through the Lovasz local lemma

Heng Guo, Mark Jerrum, Jingcheng Liu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

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	https://doi.org/10.1145/3055399.3055410
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	http://acm-stoc.org/stoc2017/

Access to Document

10.1145/3055399.3055410

PRSAccepted author manuscript, 288 KBLicence: Creative Commons: Attribution (CC-BY)

http://doi.acm.org/10.1145/3055399.3055410

Cite this

@inproceedings{77d43f4150e24ea581f40940b5e9bc77,

title = "Uniform sampling through the Lovasz local lemma",

abstract = "We propose a new algorithmic framework, called “partial rejection sampling”, todraw 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{\'a}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.",

author = "Heng Guo and Mark Jerrum and Jingcheng Liu",

year = "2017",

month = jun,

day = "23",

doi = "10.1145/3055399.3055410",

language = "English",

pages = "342--355",

booktitle = "Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017",

publisher = "ACM",

note = "STOC 2017 Theory Fest: 49th Annual ACM Symposium on the Theory of Computing ; Conference date: 19-06-2017 Through 23-06-2017",

url = "http://acm-stoc.org/stoc2017/",

}

Guo, H, Jerrum, M & Liu, J 2017, Uniform sampling through the Lovasz local lemma. in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. ACM, pp. 342-355, STOC 2017 Theory Fest: 49th Annual ACM Symposium on the Theory of Computing, Montreal, Canada, 19/06/17. https://doi.org/10.1145/3055399.3055410

TY - GEN

T1 - Uniform sampling through the Lovasz local lemma

AU - Guo, Heng

AU - Jerrum, Mark

AU - Liu, Jingcheng

PY - 2017/6/23

Y1 - 2017/6/23

N2 - We propose a new algorithmic framework, called “partial rejection sampling”, todraw 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.

AB - We propose a new algorithmic framework, called “partial rejection sampling”, todraw 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.

U2 - 10.1145/3055399.3055410

DO - 10.1145/3055399.3055410

M3 - Conference contribution

SP - 342

EP - 355

BT - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017

PB - ACM

T2 - STOC 2017 Theory Fest: 49th Annual ACM Symposium on the Theory of Computing

Y2 - 19 June 2017 through 23 June 2017

ER -

Uniform sampling through the Lovasz local lemma

Abstract

Conference

Access to Document

Fingerprint

Cite this