37 citations · 171 across the 30 of their papers we have counts for
5 papers · 1 filter
Fast sampling and counting k-SAT solutions in the local lemma regime
Weiming Feng, Heng Guo, Yitong Yin +1
We give new algorithms based on Markov chains to sample and approximately count satisfying assignments to -uniform CNF formulas where each variable appears at most times. Fo…
Counting solutions to random CNF formulas
Andreas Galanis, Leslie Ann Goldberg, Heng Guo +1
We give the first efficient algorithm to approximately count the number of solutions in the random -SAT model when the density of the formula scales exponentially with . The…
Zeros of ferromagnetic 2-spin systems
Heng Guo, Jingcheng Liu, Pinyan Lu
We study zeros of the partition functions of ferromagnetic 2-state spin systems in terms of the external field, and obtain new zero-free regions of these systems via a refinement o…
Perfect sampling from spatial mixing
Weiming Feng, Heng Guo, Yitong Yin
We introduce a new perfect sampling technique that can be applied to general Gibbs distributions and runs in linear time if the correlation decays faster than the neighborhood grow…
Modified log-Sobolev inequalities for strongly log-concave distributions
Mary Cryan, Heng Guo, Giorgos Mousa
We show that the modified log-Sobolev constant for a natural Markov chain which converges to an -homogeneous strongly log-concave distribution is at least . Applications in…