Learning CNF formulas from uniform random solutions in the local lemma regime
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 20 of its 67 references that are in the map. First posted on arXiv 4 Nov 2025.
Builds on
20 of 67 references.
References · 20
- 2014Efficiently learning Ising models on arbitrary graphscited by 50
- 2016Interaction Screening: Efficient and Sample-Optimal Learning of Ising Modelscited by 43
- 2017Learning Graphical Models Using Multiplicative Weightscited by 43
- 2021Properly learning decision trees in almost polynomial timecited by 20
- 2023A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Widthcited by 13
- 2014Structure learning of antiferromagnetic Ising modelscited by 8
- 2024Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamicscited by 8
- 2023Learning Hard-Constrained Models with One Samplecited by 7
- 2020Sampling Constraint Satisfaction Solutions in the Local Lemma Regimecited by 6
- 2019Fast sampling and counting k-SAT solutions in the local lemma regimecited by 5
- 2024Learning the Sherrington-Kirkpatrick Model Even at Low Temperaturecited by 5
- 2017Structure Learning of H-coloringscited by 4
8 more
- 2021Perfect Sampling for (Atomic) Lov'asz Local Lemmacited by 4
- 2022Deterministic counting Lov'asz local lemma beyond linear programmingcited by 4
- 2020Towards the sampling Lov'asz Local Lemmacited by 3
- 2019Counting solutions to random CNF formulascited by 2
- 2023A Sampling Lov'asz Local Lemma for Large Domain Sizescited by 2
- 2025DNF Learning via Locally Mixing Random Walkscited by 2
- 2022Inapproximability of Counting Independent Sets in Linear Hypergraphscited by 1
- 2025Faster exact learning of k-term DNFs with membership and equivalence queriescited by 1
Built on by
Citing papers per year: 2026: 2.
2 papers.