Heng Guo 0001

FOCS Conference 2025 Conference Paper

Deterministic Counting from Coupling Independence

• Xiaoyu Chen
• Weiming Feng 0001
• Heng Guo 0001
• Xinyuan Zhang
• Zongrui Zou

We show that spin systems with bounded degrees and coupling independence admit fully polynomial time approximation schemes (FPTAS). We design a new recursive deterministic counting algorithm to achieve this. As applications, we give the first FPTASes for q-colourings on graphs of bounded maximum degree $\Delta \geq 3$, when $q \geq\left(11 / 6-\varepsilon_{0}\right) \Delta$ for some small $\varepsilon_{0} \approx 10^{-5}$, or when $\Delta \geq 125$ and $q \geq 1. 809 \Delta$, and on graphs with sufficiently large (but constant) girth, when $q \geq \Delta+3$. These bounds match the current best randomised approximate counting algorithms by Chen, Delcourt, Moitra, Perarnau, and Postle (2019), Carlson and Vigoda (2024), and Chen, Liu, Mani, and Moitra (2023), respectively.

FOCS Conference 2023 Conference Paper

Towards derandomising Markov chain Monte Carlo

• Weiming Feng 0001
• Heng Guo 0001
• Chunyang Wang 0003
• Jiaheng Wang 0002
• Yitong Yin

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 distributions. For the latter task, we introduce a method called coupling towards the past that can, in logarithmic time, evaluate one or a constant number of variables from a stationary Markov chain state. Since there are at most logarithmic random choices, this leads to very simple derandomisation. We provide two applications of this framework, namely efficient deterministic approximate counting algorithms for hypergraph independent sets and hypergraph colourings, under local lemma type conditions matching, up to lower order factors, their state-of-the-art randomised counterparts.

SODA Conference 2021 Conference Paper

Rapid Mixing from Spectral Independence beyond the Boolean Domain

• Weiming Feng 0001
• Heng Guo 0001
• Yitong Yin
• Chihao Zhang 0001

We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [2]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations, and implies that the corresponding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper q -colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided q ≥ ( α ∗ + δ )Δ where α ∗ ≈ 1. 763 is the unique solution to α ∗ = exp (1/ α ∗) and δ > 0 is any constant. This is the first efficient algorithm for sampling proper q -colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [19].

STOC Conference 2020 Conference Paper

Fast sampling and counting k-SAT solutions in the local lemma regime

• Weiming Feng 0001
• Heng Guo 0001
• Yitong Yin
• Chihao Zhang 0001

We give new algorithms based on Markov chains to sample and approximately count satisfying assignments to k -uniform CNF formulas where each variable appears at most d times. For any k and d satisfying kd < n o (1) and k ≥ 20log k + 20log d + 60, the new sampling algorithm runs in close to linear time, and the counting algorithm runs in close to quadratic time.

SODA Conference 2020 Conference Paper

Zeros of ferromagnetic 2-spin systems

• Heng Guo 0001
• Jingcheng Liu 0001
• Pinyan Lu

FOCS Conference 2019 Conference Paper

Modified log-Sobolev Inequalities for Strongly Log-Concave Distributions

• Mary Cryan
• Heng Guo 0001
• Giorgos Mousa

We show that the modified log-Sobolev constant for a natural Markov chain which converges to an r-homogeneous strongly log-concave distribution is at least 1/r. Applications include an asymptotically optimal mixing time bound for the bases-exchange walk for matroids, and a concentration bound for Lipschitz functions over these distributions.

SODA Conference 2019 Conference Paper

Zeros of Holant problems: locations and algorithms

• Heng Guo 0001
• Chao Liao
• Pinyan Lu
• Chihao Zhang 0001

We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised second order recurrence modulo a couple of exceptional cases. As a consequence, any non-negative Holant problem on cubic graphs has an efficient approximation algorithm unless the problem is equivalent to approximately counting perfect matchings, a central open problem in the area. This is in sharp contrast to the computational phase transition shown by 2-state spin systems on cubic graphs. Our main technique is the recently established connection between zeros of graph polynomials and approximate counting. We also use the “winding” technique to deduce the second result on cubic graphs.

STOC Conference 2018 Conference Paper

Counting hypergraph colourings in the local lemma regime

• Heng Guo 0001
• Chao Liao
• Pinyan Lu
• Chihao Zhang 0001

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of q -colorings for k -uniform hypergraphs with maximum degree Δ if k ≥ 28 and q > 315Δ 14/ k −14 . We also obtain a polynomial-time almost uniform sampler if q >798Δ 16/ k −16/3 . These are the first approximate counting and sampling algorithms in the regime q ≪Δ (for large Δ and k ) without any additional assumptions. Our method is based on the recent work of Moitra (STOC, 2017). One important contribution of ours is to remove the dependency of k and Δ in Moitra’s approach.

SODA Conference 2017 Conference Paper

Random cluster dynamics for the Ising model is rapidly mixing

• Heng Guo 0001
• Mark Jerrum

We show for the first time that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 is bounded by a polynomial in the size of the underlying graph. As a consequence, the Swendsen- Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound.

STOC Conference 2017 Conference Paper

Uniform sampling through the Lovasz local lemma

• Heng Guo 0001
• Mark Jerrum
• Jingcheng Liu 0001

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 occurring. Our framework builds (perhaps surprising) new connections between the variable framework of the Lovász Local Lemma and some clas- sical sampling algorithms such as the “cycle-popping” algorithm for rooted spanning trees by Wilson. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences.

FOCS Conference 2015 Conference Paper

A Holant Dichotomy: Is the FKT Algorithm Universal?

• Jin-Yi Cai
• Zhiguo Fu
• Heng Guo 0001
• Tyson Williams

We prove a complexity dichotomy for complex-weighted Holant problems with an arbitrary set of symmetric constraint functions on Boolean variables. In the study of counting complexity, such as #CSP, there are problems which are #P-hard over general graphs but P-time solvable over planar graphs. A recurring theme has been that a holographic reduction [36] to FKT precisely captures these problems. This dichotomy answers the question: Is this a universal strategy? Surprisingly, we discover new planar tractable problems in the Holant framework (which generalizes #CSP) that are not expressible by a holographic reduction to FKT. In particular, the putative form of a dichotomy for planar Holant problems is false. Nevertheless, we prove a dichotomy for #CSP 2, a variant of #CSP where every variable appears even times, that the presumed universality holds for #CSP 2. This becomes an important tool in the proof of the full dichotomy, which refutes this universality in general. The full dichotomy says that the new P-time algorithms and the strategy of holographic reductions to FKT together are universal for these locally defined counting problems. As a special case of our new planar tractable problems, counting perfect matchings (#PM) over k-uniform hypergraphs is P-time computable when the incidence graph is planar and k ≥ 5. The same problem is #P-hard when k = 3 or k = 4, also a consequence of the dichotomy. More generally, over hypergraphs with specified hyperedge sizes and the same planarity assumption, #PM is P-time computable if the greatest common divisor (gcd) of all hyperedge sizes is at least 5.

FOCS Conference 2014 Conference Paper

The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems

• Jin-Yi Cai
• Heng Guo 0001
• Tyson Williams

We show that an effective version of Siegel's Theorem on finiteness of integer solutions for a specific algebraic curve and an application of elementary Galois theory are key ingredients in a complexity classification of some Holant problems. These Holant problems, denoted by Holant(f), are defined by a symmetric ternary function f that is invariant under any permutation of the κ ≥ 3 domain elements. We prove that Holant(f) exhibits a complexity dichotomy. The hardness, and thus the dichotomy, holds even when restricted to planar graphs. A special case of this result is that counting edge κ-colorings is #P-hard over planar 3-regular multigraphs for all κ ≥ 3. In fact, we prove that counting edge κ-colorings is #P-hard over planar r-regular multigraphs for all κ ≥ r ≥ 3. The problem is polynomial-time computable in all other parameter settings. The proof of the dichotomy theorem for Holant(f) depends on the fact that a specific polynomial p(x, y) has an explicitly listed finite set of integer solutions, and the determination of the Galois groups of some specific polynomials. In the process, we also encounter the Tutte polynomial, medial graphs, Eulerian partitions, Puiseux series, and a certain lattice condition on the (logarithm of) the roots of polynomials.

STOC Conference 2013 Conference Paper

A complete dichotomy rises from the capture of vanishing signatures: extended abstract

• Jin-Yi Cai
• Heng Guo 0001
• Tyson Williams

We prove a complexity dichotomy theorem for Holant problems over an arbitrary set of complex-valued symmetric constraint functions {F} on Boolean variables. This extends and unifies all previous dichotomies for Holant problems on symmetric constraint functions (taking values without a finite modulus). We define and characterize all symmetric vanishing signatures. They turned out to be essential to the complete classification of Holant problems. The dichotomy theorem has an explicit tractability criterion. A Holant problem defined by a set of constraint functions {F} is solvable in polynomial time if it satisfies this tractability criterion, and is #P-hard otherwise. The tractability criterion can be intuitively stated as follows: A set {F} is tractable if (1) every function in {F} has arity at most two, or (2) {F} is transformable to an affine type, or (3) {F} is transformable to a product type, or (4) {F} is vanishing, combined with the right type of binary functions, or (5) {F} belongs to a special category of vanishing type Fibonacci gates. The proof of this theorem utilizes many previous dichotomy theorems on Holant problems and Boolean #CSP. Holographic transformations play an indispensable role, not only as a proof technique, but also in the statement of the dichotomy criterion.

CSL Conference 2009 Conference Paper

On Model Checking Boolean BI

• Heng Guo 0001
• Hanpin Wang
• Zhongyuan Xu
• Yongzhi Cao

Abstract The logic of bunched implications (BI), introduced by O’Hearn and Pym, is a substructural logic which freely combines additive and multiplicative implications. Boolean BI (BBI) denotes BI with classical interpretation of additives and its model is the commutative monoid. We show that when the monoid is finitely generated and propositions are recursively defined, or the monoid is infinitely generated and propositions are restricted to generator propositions, the model checking problem is undecidable. In the case of finitely related monoid and generator propositions, the model checking problem is EXPSPACE-complete.