Learning CNF formulas from uniform random solutions in the local lemma regime
This addresses the problem of efficiently learning Boolean structures from limited data for researchers in computational learning theory, though it is incremental as it revisits and improves an existing algorithm.
The paper tackles learning k-CNF formulas from uniform random solutions, showing that Valiant's algorithm can exactly learn such formulas under Lovász local lemma conditions with O(log n) samples, and random k-CNFs near the satisfiability threshold with O~(n^{exp(-sqrt(k))}) samples, improving previous O(n^k) complexity.
We study the problem of learning a $n$-variables $k$-CNF formula $Φ$ 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ász local lemma type conditions, from $O(\log n)$ samples; and (2) random $k$-CNFs near the satisfiability threshold, from $\widetilde{O}(n^{\exp(-\sqrt{k})})$ samples. These results significantly improve the previous $O(n^k)$ 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.