37 citations · 171 across the 30 of their papers we have counts for
35 papers
Optimal Simulated Annealing for Partition Function Estimation
Heng Guo, Hongyang Liu, Xiongxin Yang +2
In this note, we give a simple analysis of a non-adaptive simulated annealing algorithm for estimating the partition function of Gibbs distributions. This yields the most efficient…
Approximate Counting for Spin Systems in Sub-Quadratic Time
Konrad Anand, Weiming Feng, Graham Freifeld +2
We present two randomised approximate counting algorithms with running time for some constant and accuracy : (1) for the h…
Towards derandomising Markov chain Monte Carlo
Weiming Feng, Heng Guo, Chunyang Wang +2
We present a new framework to derandomise certain Markov chain Monte Carlo (MCMC) algorithms. As in MCMC, we first reduce counting problems to sampling from a sequence of marginal…
Fast sampling of satisfying assignments from random -SAT with applications to connectivity
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg +4
We give a nearly linear-time algorithm to approximately sample satisfying assignments in the random -SAT model when the density of the formula scales exponentially with . The…
Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
Weiming Feng, Heng Guo, Jiaheng Wang
We study the sampling problem for the ferromagnetic Ising model with consistent external fields, and in particular, Swendsen-Wang dynamics on this model. We introduce a new grand m…
Improved bounds for randomly colouring simple hypergraphs
Weiming Feng, Heng Guo, Jiaheng Wang
We study the problem of sampling almost uniform proper -colourings in -uniform simple hypergraphs with maximum degree . For any , if and $q \…
Inapproximability of counting hypergraph colourings
Andreas Galanis, Heng Guo, Jiaheng Wang
Recent developments in approximate counting have made startling progress in developing fast algorithmic methods for approximating the number of solutions to constraint satisfaction…
Counting vertices of integral polytopes defined by facets
Heng Guo, Mark Jerrum
We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes…
Local-to-Global Contraction in Simplicial Complexes
Heng Guo, Giorgos Mousa
We give a local-to-global principle for relative entropy contraction in simplicial complexes. This is similar to the local-to-global principle for variances obtained by Alev and La…
Rapid mixing from spectral independence beyond the Boolean domain
Weiming Feng, Heng Guo, Yitong Yin +1
We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) from the Boolean domain to general discrete domains. This property characterises…
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…
Zeros of Holant problems: locations and algorithms
Heng Guo, Chao Liao, Pinyan Lu +1
We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised sec…
Approximately counting bases of bicircular matroids
Heng Guo, Mark Jerrum
We give a fully polynomial-time randomised approximation scheme (FPRAS) for the number of bases in a bicircular matroids. This is a natural class of matroids for which counting bas…
Tight bounds for popping algorithms
Heng Guo, Kun He
We sharpen run-time analysis for algorithms under the partial rejection sampling framework. Our method yields improved bounds for: the cluster-popping algorithm for approximating a…
Perfect simulation of the Hard Disks Model by Partial Rejection Sampling
Heng Guo, Mark Jerrum
We present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples…
Counting hypergraph colorings in the local lemma regime
Heng Guo, Chao Liao, Pinyan Lu +1
We give a fully polynomial-time approximation scheme (FPTAS) to count the number of -colorings for -uniform hypergraphs with maximum degree if and $q >357Δ^{\fr…
A polynomial-time approximation algorithm for all-terminal network reliability
Heng Guo, Mark Jerrum
We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that, in a undirecte…
Clifford Gates in the Holant Framework
Jin-Yi Cai, Heng Guo, Tyson Williams
We show that the Clifford gates and stabilizer circuits in the quantum computing literature, which admit efficient classical simulation, are equivalent to affine signatures under a…
Layerwise Systematic Scan: Deep Boltzmann Machines and Beyond
Heng Guo, Kaan Kara, Ce Zhang
For Markov chain Monte Carlo methods, one of the greatest discrepancies between theory and system is the scan order - while most theoretical development on the mixing time analysis…
Uniform Sampling through the Lovász Local Lemma
Heng Guo, Mark Jerrum, Jingcheng Liu
We propose a new algorithmic framework, called "partial rejection sampling", to draw samples exactly from a product distribution, conditioned on none of a number of bad events occu…