Uniform Sampling Through the Lovász Local Lemma

DOI10.1145/3310131zbMath1425.68451OpenAlexW2914272038WikidataQ125003541 ScholiaQ125003541MaRDI QIDQ5244390

Heng Guo, Jing-Cheng Liu, Mark R. Jerrum

Publication date: 21 November 2019

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3310131

zbMATH Keywords

exact samplingLovász local lemma\#Sat

Mathematics Subject Classification ID

Combinatorial probability (60C05) Randomized algorithms (68W20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (11)

Counting and sampling orientations on chordal graphs ⋮ Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing ⋮ Counting Solutions to Random CNF Formulas ⋮ Perfect sampling from spatial mixing ⋮ New bounds for the Moser‐Tardos distribution ⋮ Perfect simulation of the hard disks model by partial rejection sampling ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ Approximately counting bases of bicircular matroids ⋮ Dynamic Sampling from Graphical Models ⋮ Implementations and the independent set polynomial below the Shearer threshold ⋮ Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs

This page was built for publication: Uniform Sampling Through the Lovász Local Lemma