Learning CNF formulas from uniform random solutions in the local lemma regime

Weiming Feng, Xiongxin Yang, Yixiao Yu +1

We study the problem of learning a $n$-variables $k$-CNF formula $\Phi$ from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) w…