6 papers
An -Time Sampler for Zero-Field Ferromagnetic Ising Models
Weiming Feng, Heng Guo, Yiyao Zhang
We give an approximate sampler for ferromagnetic Ising models with no field on arbitrary graphs that runs in time , w…
A Counting and Sampling Lovász Local Lemma
Hongyang Liu, Chunyang Wang, Yitong Yin +2
We establish counting and sampling analogues of the Lovász Local Lemma: we give efficient algorithms for approximately counting and exactly sampling satisfying assignments of gener…
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,…
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 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…
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…