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

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\ge 1$, under $k\gtrsim (1+1\mathrm{/}t)\log d$, Valiant’s algorithm achieves total variation error $\epsilon$ with $\tilde{O}(n^{\lceil t\rceil }\mathrm{/}\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 $\tilde{\mathrm{\Omega }}(n\mathrm{/}\epsilon )$.