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

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\geq1$, under $k\gtrsim(1+1/t)\log d$, Valiant's algorithm achieves total variation error $\varepsilon$ with $\widetilde{O}(n^{\lceil 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 $\widetildeΩ(n/\varepsilon)$.