Uniform Sampling Through the Lovasz Locál Lemma

Heng Guo; Mark Jerrum; Jingcheng Liu

doi:10.1145/3310131

Uniform Sampling Through the Lovasz Locál Lemma

Heng Guo, Mark Jerrum, Jingcheng Liu

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	18
Number of pages	31
Journal	Journal of the ACM
Volume	66
Issue number	3
Early online date	12 Apr 2019
DOIs	https://doi.org/10.1145/3310131
Publication status	Published - 1 Jun 2019

Access to Document

10.1145/3310131Licence: All Rights Reserved

PRSAccepted author manuscript, 280 KB

https://dl.acm.org/doi/10.1145/3310131Licence: All Rights Reserved

Heng Guo
- School of Informatics - Reader in Algorithms and Complexity
- Laboratory for Foundations of Computer Science - Lecturer in Algorithms and Complexity
- Foundations of Computation
Person: Academic: Research Active (Teaching)

Cite this

@article{77046a3b6fad42d3809ce9a3c0308d9c,

title = "Uniform Sampling Through the Lovasz Loc{\'a}l Lemma",

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{\'a}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.",

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

year = "2019",

month = jun,

day = "1",

doi = "10.1145/3310131",

language = "English",

volume = "66",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "3",

}

TY - JOUR

T1 - Uniform Sampling Through the Lovasz Locál Lemma

AU - Guo, Heng

AU - Jerrum, Mark

AU - Liu, Jingcheng

PY - 2019/6/1

Y1 - 2019/6/1

N2 - 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.

AB - 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.

U2 - 10.1145/3310131

DO - 10.1145/3310131

M3 - Article

SN - 0004-5411

VL - 66

JO - Journal of the ACM

JF - Journal of the ACM

IS - 3

M1 - 18

ER -

Uniform Sampling Through the Lovasz Locál Lemma

Abstract

Access to Document

Fingerprint

Profiles

Heng Guo

Cite this