Improved Bounds for Sampling Solutions of Random CNF Formulas
Kun He, Kewen Wu, Kuan Yang
Abstract
Let Φ be a random k-CNF formula on n variables and m clauses, where each clause is a disjunction of k literals chosen independently and uniformly. Our goal is to sample an approximately uniform solution of Φ (or equivalently, approximate the partition function of Φ).
Let α = m/n be the density. The previous best algorithm runs in time n poly(k,α) for any α 2 k/300 [Galanis, Goldberg, Guo, and Yang, SIAM J. Comput.'21]. Our result significantly improves both bounds by providing an almost-linear time sampler for any α 2 k/3 .
The density α captures the average degree in the random formula. In the worst-case model with bounded maximum degree, current best efficient sampler works up to degree bound 2 k/5 [He, Wang, and Yin, FOCS'22 and SODA'23], which is, for the first time, superseded by its averagecase counterpart due to our 2 k/3 bound. Our result is the first progress towards establishing the intuition that the solvability of the average-case model (random k-CNF formula with bounded average degree) is better than the worst-case model (standard k-CNF formula with bounded maximal degree) in terms of sampling solutions.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime cites Fast sampling and counting k-SAT solutions in the local lemma regime
- Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime cites A Sampling Lovász Local Lemma for Large Domain Sizes
- Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime cites Sampling constraint satisfaction solutions in the local lemma regime
- Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime cites Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time
- Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime cites Deterministic counting Lovász local lemma beyond linear programming
- Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime cites Fast sampling and counting k-SAT solutions in the local lemma regime
- Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime cites A Sampling Lovász Local Lemma for Large Domain Sizes
- Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime cites Sampling constraint satisfaction solutions in the local lemma regime
- Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime cites Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time
- Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime cites Learning Hard-Constrained Models with One Sample
- Learning CNF Formulas from Uniform Random Solutions in the Local Lemma Regime cites Deterministic counting Lovász local lemma beyond linear programming
- A Sampling Lovász Local Lemma for Large Domain Sizes cites Sampling constraint satisfaction solutions in the local lemma regime
- A Sampling Lovász Local Lemma for Large Domain Sizes cites Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time
- A Sampling Lovász Local Lemma for Large Domain Sizes cites Deterministic counting Lovász local lemma beyond linear programming
- Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time cites Sampling constraint satisfaction solutions in the local lemma regime
- Learning Hard-Constrained Models with One Sample cites Fast sampling and counting k-SAT solutions in the local lemma regime
- Learning Hard-Constrained Models with One Sample cites Sampling constraint satisfaction solutions in the local lemma regime
- Learning Hard-Constrained Models with One Sample cites Deterministic counting Lovász local lemma beyond linear programming
- Learning Hard-Constrained Models with One Sample cites The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
- Deterministic counting Lovász local lemma beyond linear programming cites Sampling constraint satisfaction solutions in the local lemma regime
- Deterministic counting Lovász local lemma beyond linear programming cites Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time
Cited by top-tier papers4
- A Sampling Lovász Local Lemma for Large Domain SizesChunyang Wang, Yitong YinFOCS 2024 · 5 citations
- Learning CNF Formulas from Uniform Random Solutions in the Local Lemma RegimeWeiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao ZhangSTOC 2026 · 2 citations
- Learning Hard-Constrained Models with One SampleAndreas Galanis, Alkis Kalavasis, Anthimos Vardis KandirosSODA 2024 · 1 citation
- Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma RegimeJingcheng Liu, Yixiao YuSTOC 2026
Builds on6
- The Algorithmic Phase Transition of Random k-SAT for Low Degree PolynomialsGuy Bresler, Brice HuangFOCS 2021 · 32 citations
- Sampling constraint satisfaction solutions in the local lemma regimeWeiming Feng, Kun He, Yitong YinSTOC 2021 · 16 citations
- Fast sampling and counting k-SAT solutions in the local lemma regimeWeiming Feng, Heng Guo, Yitong Yin, Chihao ZhangSTOC 2020 · 13 citations
- Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear timeKun He, Chunyang Wang, Yitong YinFOCS 2022 · 8 citations
- Deterministic counting Lovász local lemma beyond linear programmingKun He, Chunyang Wang, Yitong YinSODA 2023 · 7 citations
Related papers
- Counting Random k-SAT near the Satisfiability ThresholdZongchen Chen, Aditya Lonkar, Chunyang Wang, Kuan Yang et al.STOC 2025 · 2 citations
- From Algorithms to Connectivity and Back: Finding a Giant Component in Random k-SATZongchen Chen, Nitya ManiSODA 2023 · 3 citations
- Towards the sampling Lovász Local LemmaVishesh Jain, Huy Tuan Pham, Thuy-Duong VuongFOCS 2021 · 17 citations
- Analysis of Pure Literal Elimination Rule for Non-uniform Random (MAX) k-SAT Problem with an Arbitrary Degree DistributionOleksii Omelchenko, Andrei A. BulatovAAAI 2022
- Perfectly sampling k ≥ (8/3 + o(1))Δ-colorings in graphsVishesh Jain, Ashwin Sah, Mehtaab SawhneySTOC 2021 · 3 citations
