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

arXiv:2609.15268v1 Announce Type: new 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 tgeq1, under kgtrsim(1+1/t)log d, Valiant's algorithm achieves total variation error arepsilon with widetilde{O}(n^{lceil t rceil}/arepsilon) 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 widetildeOmega(n/arepsilon).

Source: arXiv cs.LG | 2026-09-15