{"ID":2846187,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.02487","arxiv_id":"2511.02487","title":"Learning CNF formulas from uniform random solutions in the local lemma regime","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2511.02487","url_pdf":"https://arxiv.org/pdf/2511.02487v1","authors":"[\"Weiming Feng\",\"Xiongxin Yang\",\"Yixiao Yu\",\"Yiyao Zhang\"]","published":"2025-11-04T11:22:05Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}