3 papers
cs.DS2026
A Counting Lovász Local Lemma
Hongyang Liu, Chunyang Wang, Yitong Yin +2
We establish a counting analogue of the Lovász Local Lemma: we give polynomial-time algorithms for approximately counting satisfying assignments of general constraint satisfaction…
cs.LG2026
Learning under Locally Sampleable Graphical Models
Weiming Feng, Xiongxin Yang, Yixiao Yu +1
The problem of learning constant-depth circuits holds profound implications for computational learning theory. In a seminal result, by introducing the low-degree algorithm, Linial,…
cs.DS2025
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 -variables -CNF formula from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) w…