# Learning CNF formulas from uniform random solutions in the local lemma regime

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 67 references that are in the map.
- First posted on arXiv 4 Nov 2025.

## Builds on (most cited first, 20 of 20)

- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [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)
- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Structure learning of antiferromagnetic Ising models](https://mlsanity.com/paper/1412.1443/) (2014)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [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)
- [Learning the Sherrington-Kirkpatrick Model Even at Low Temperature](https://mlsanity.com/paper/2411.11174/) (2024)
- [Structure Learning of H-colorings](https://mlsanity.com/paper/1708.05118/) (2017)
- [Perfect Sampling for (Atomic) Lov'asz Local Lemma](https://mlsanity.com/paper/2107.03932/) (2021)
- [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)
- [Counting solutions to random CNF formulas](https://mlsanity.com/paper/1911.07020/) (2019)
- [A Sampling Lov'asz Local Lemma for Large Domain Sizes](https://mlsanity.com/paper/2307.14872/) (2023)
- [DNF Learning via Locally Mixing Random Walks](https://mlsanity.com/paper/2505.18839/) (2025)
- [Inapproximability of Counting Independent Sets in Linear Hypergraphs](https://mlsanity.com/paper/2212.03072/) (2022)
- [Faster exact learning of k-term DNFs with membership and equivalence queries](https://mlsanity.com/paper/2507.20336/) (2025)

## Built on by (most cited first, 2 of 2)

- [Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue](https://mlsanity.com/paper/2607.22889/) (2026)
- [Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm](https://mlsanity.com/paper/2609.15268/) (2026)

## Abstract (arXiv)

We study the problem of learning a n-variables k-CNF formula Phi from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) with k-wise hard constraints. Revisiting Valiant's algorithm (Commun. ACM'84), we show that it can exactly learn (1) k-CNFs with bounded clause intersection size under Lov'asz local lemma type conditions, from O(log n) samples; and (2) random k-CNFs near the satisfiability threshold, from widetildeO(n^exp(-√k)) samples. These results significantly improve the previous O(nk) sample complexity. We further establish new information-theoretic lower bounds on sample complexity for both exact and approximate learning from i.i.d. uniform random solutions.