# Heng Guo 郭珩

School of Mathematical Sciences

Queen Mary, University of London

Mile End Road

London, E1 4NS, UK

email: h.guo AT qmul ac uk

## About Me

I am currently a postdoc in the School of Mathematical Sciences of Queen Mary, University of London, supervised by Prof. Mark Jerrum.

My research interest lies in theoretical computer science. I am particularly interested in mapping the complexity of counting problems. Typical problems include computing marginal probabilities and expectations of random variables, the evaluation of partition functions, etc. During this journey I inadvertently made some progress to understand the power of various algorithms, exact and approximate, deterministic and randomized alike.

For a list of publications, see the research page (with pdfs and slides, if available).

## Selected Research

## **Computational Complexity Classifications**

*A Holant Dichotomy: Is the FKT Algorithm Universal?* (with Jin-Yi Cai, Zhiguo Fu, and Tyson Williams), FOCS 2015

*A Complete Dichotomy Rises from the Capture of Vanishing Signatures* (with Jin-Yi Cai and Tyson Williams), SIAM J. Comput., 45(5), 1671-1728, 2016

The goal of computational complexity is to understand the intrinsic difficulty of various problems. Instead of looking at individual problems or asking overly broad questions, we turn to problems within certain expressive yet specific frameworks. The Holant framework, inspired by the seminal work of Valiant on holographic algorithms, include fundamental questions in many areas. One way to formulate the Holant is to evaluate the contraction of a given tensor network. In the two work above, we establish complete classifications when the defining constraint functions (or tensors) are symmetric in both the general and planar settings.

## **Rapid Mixing of Random Cluster Dynamics**

*Random Cluster Dynamics for the Ising Model is Rapidly Mixing* (with Mark Jerrum), SODA 2017

On the random cluster model at q = 2, we establish a mixing time upper bound for the Glauber dynamics that is polynomial in the size of the underlying graph. This result, through a comparison result of Ullrich (2014), implies that the Swendsen-Wang (1987) algorithm for ferromagnetic Ising models is always rapidly mixing, which has been conjectured by Sokal. Note that our bound is much larger than the conjectured optimal upper bound O(n^0.25) due to Peres.

## **Uniform Sampling and the Lovasz Local Lemma**

*Uniform Sampling through the Lovasz Local Lemma* (with Mark Jerrum and Jingcheng Liu), STOC 2017

The Lovasz Local Lemma is a classical gem in combinatorics to show the existence of “perfect” objects under dependency conditions. The local lemma is made algorithmic by Moser and Tardos (2010), showing that one can find a perfect object efficiently under the same conditions. However, it is still not clear how to generate these perfect objects uniformly at random. We showed that for extremal instances, the output of the Moser-Tardos algorithm is in fact uniform over all perfect objects. Furthermore, we found a new variant whose output is uniform in general, but to keep it efficient, stronger conditions have to be assumed.