Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm
cs.LG, cs.DS
Submitted: 2026-09-14
Updated: 2026-09-14
License: http://creativecommons.org/licenses/by/4.0/
The gist: We revisit Valiant's algorithm (Commun.
Terminology
Abstract
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 at least1, under k (1+1/t) d, Valiant's algorithm achieves total variation error epsilon with (n t/epsilon) 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 Ω(n/epsilon).
Sources
- Learning $\mathsf{AC}^0$ Under Graphical Models
- Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models
- A Counting Lov'asz Local Lemma
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks