mlsanityData to 14 Oct 2026

Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm

arXiv 2609.15268 ↗First posted 14 Sep 2026cs.LG cs.DScited by 0

Not on the map. Why?

Abstract (arXiv)

We revisit Valiant's algorithm (Commun. ACM'84) for learning n-variable CNF formulas with clause size k and variable degree d from i.i.d. uniform random solutions in the local lemma regime. For fixed t≥1, under kgtrsim(1+1/t)log d, Valiant's algorithm achieves total variation error varepsilon with widetildeO(nlceil t rceil/varepsilon) sample complexity. For t>1, we prove a matching lower bound for Valiant's algorithm. At t=1 (covering 0<t<1), we show Valiant's algorithm has optimal sample complexity up to logarithmic factors by an information-theoretic lower bound widetildeOmega(n/varepsilon).

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 19 of its 35 references that are in the map. First posted on arXiv 14 Sep 2026.

Builds on

19 of 35 references.

References · 19

  1. 2016Interaction Screening: Efficient and Sample-Optimal Learning of Ising Modelscited by 43
  2. 2017Learning Graphical Models Using Multiplicative Weightscited by 43
  3. 2017Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applicationscited by 21
  4. 2021Properly learning decision trees in almost polynomial timecited by 20
  5. 2014Learning graphical models from the Glauber dynamicscited by 14
  6. 2023A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Widthcited by 14
  7. 2016Uniform Sampling through the Lov'asz Local Lemmacited by 9
  8. 2024Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamicscited by 8
  9. 2020Sampling Constraint Satisfaction Solutions in the Local Lemma Regimecited by 6
  10. 2019Fast sampling and counting k-SAT solutions in the local lemma regimecited by 5
  11. 2017Structure Learning of H-coloringscited by 4
  12. 2019Learning from satisfying assignments under continuous distributionscited by 4
7 more
  1. 2022Deterministic counting Lov'asz local lemma beyond linear programmingcited by 4
  2. 2020Towards the sampling Lov'asz Local Lemmacited by 3
  3. 2025Learning CNF formulas from uniform random solutions in the local lemma regimecited by 2
  4. 2017Counting hypergraph colorings in the local lemma regimecited by 1
  5. 2021Inapproximability of counting hypergraph colouringscited by 1
  6. 2022Sampling Lov'asz Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Timecited by 1
  7. 2026Learning mathsfAC0 under Locally Sampleable Graphical Modelscited by 1

Built on by

Not cited yet.