Uniform Sampling Through the Lovasz Local Lemma

被引：32

作者：

Guo, Heng ^{[1
]}

Jerrum, Mark ^{[2
]}

Liu, Jingcheng ^{[3
]}

机构：

[1] Univ Edinburgh, Sch Informat, Edinburgh EH8 9AB, Midlothian, Scotland

[2] Queen Mary Univ London, Sch Math Sci, London E1 4NS, England

[3] Univ Calif Berkeley, Dept EECS, Berkeley, CA 94720 USA

来源：

JOURNAL OF THE ACM | 2019年 / 66卷 / 03期

基金：

英国工程与自然科学研究理事会;

关键词：

Exact sampling; Lovasz Local Lemma; #SAT; ALGORITHMIC APPROACH;

D O I：

10.1145/3310131

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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

引用

页数：31

共 41 条

[21]

Harris DG, 2013, STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, P685

[22] The Moser-Tardos Framework with Partial Resampling [J].

Harris, David G. ;

Srinivasan, Aravind .

2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, :469-478

[23]

Harris DavidG., 2014, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, P907, DOI [10.1137/1.9781611973402.68, DOI 10.1137/1.9781611973402.68]

[24] An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles [J].

Harvey, Nicholas J. A. ;

Vondrak, Jan .

2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2015, :1327-1345

[25]

Hermon Jonathan, 2016, ARXIV161007999

[26]

Knuth D. E., 2015, The Art of Computer Programming, Volume 4, Fascicle 6: Satisfiability., V4

[27]

Kolipaka K, 2011, ACM S THEORY COMPUT, P235

[28]

Linial N., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P331, DOI 10.1109/SFCS.1987.20

[29]

Liu Jingcheng., 2015, SODA, P1531, DOI [10.1137/1.9781611973730.101. eprint, DOI 10.1137/1.9781611973730.101.EPRINT]

[30]

Moitra Ankur, 2016, ARXIV161004317

← 1 2 3 4 5 →