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

arXiv: https://arxiv.org/abs/2609.15268 · HTML: https://mlsanity.com/paper/2609.15268/

## 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 (most cited first, 19 of 19)

- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017)
- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Learning graphical models from the Glauber dynamics](https://mlsanity.com/paper/1410.7659/) (2014)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Uniform Sampling through the Lov'asz Local Lemma](https://mlsanity.com/paper/1611.01647/) (2016)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Sampling Constraint Satisfaction Solutions in the Local Lemma Regime](https://mlsanity.com/paper/2011.03915/) (2020)
- [Fast sampling and counting k-SAT solutions in the local lemma regime](https://mlsanity.com/paper/1911.01319/) (2019)
- [Structure Learning of H-colorings](https://mlsanity.com/paper/1708.05118/) (2017)
- [Learning from satisfying assignments under continuous distributions](https://mlsanity.com/paper/1907.01619/) (2019)
- [Deterministic counting Lov'asz local lemma beyond linear programming](https://mlsanity.com/paper/2212.14847/) (2022)
- [Towards the sampling Lov'asz Local Lemma](https://mlsanity.com/paper/2011.12196/) (2020)
- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)
- [Counting hypergraph colorings in the local lemma regime](https://mlsanity.com/paper/1711.03396/) (2017)
- [Inapproximability of counting hypergraph colourings](https://mlsanity.com/paper/2107.05486/) (2021)
- [Sampling Lov'asz Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time](https://mlsanity.com/paper/2204.01520/) (2022)
- [Learning mathsfAC0 under Locally Sampleable Graphical Models](https://mlsanity.com/paper/2607.08303/) (2026)

## 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).