11 citations · 26 across the 9 of their papers we have counts for
4 papers · 2 filters
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…