5 papers
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…
Near-Optimal Parallel Approximate Counting via Sampling
David G. Harris, Vladimir Kolmogorov, Hongyang Liu +2
The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sa…
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,…
Work-Efficient Parallel Counting via Sampling
Hongyang Liu, Yitong Yin, Yiyao Zhang
A canonical approach to approximating the partition function of a Gibbs distribution via sampling is simulated annealing. This method has led to efficient reductions from counting…
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)…