Informatics Forum, 5.05A
10 Crichton Street
Edinburgh, EH8 9AB
email: hguo AT inf ed ac uk

About me

I am a reader in algorithms and complexity in the School of informatics, University of Edinburgh. Before Edinburgh, I have worked / studied in Berkeley, London, Madison, and Beijing. My hometown is Luoyang.

My research focuses on algorithms from a complexity perspective. I am particularly interested in computational counting and sampling. Typical problems include computing marginal probabilities and expectations of random variables, the evaluation of partition functions, etc. I strive to understand the boundary between problems with efficient algorithms and those without.

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

My research is supported by an ERC starting grant – NACS.

A few people I work with

Some research

I am particularly enthralled by problems that seem impossible at first sight. Some of them remain impossible after considerable thought, until the right angle is found.

Uniform sampling and the Lovász local lemma Uniform sampling through the Lovász local lemma (with Mark Jerrum and Jingcheng Liu), J. ACM, 66(3):18, 2019
A polynomial-time approximation algorithm for all-terminal network reliability (with Mark Jerrum), SIAM J. Comput, 48(3), 964-978, 2019 (also won the best paper award in ICALP 2018)

The Lovász 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, called partial rejection sampling, whose output is guaranteed to be from the desire distribution, and with faster running time than rejection sampling. Using this new framework, we manage to confirm a conjecture of Gorodezky and Pak (2014). This leads to the first polynomial-time approximation algorithm for all-terminal network reliability, which is an open problem since 1980s, and is explicitly mentioned by, for example, Welsh (1993).

The right angle here is, apparently, “the constructive Lovász Local Lemma”.
Rapid mixing of random cluster dynamics Random cluster dynamics for the Ising model is rapidly mixing (with Mark Jerrum), Ann. Appl. Probab. 28(2), 1292-1313, 2018

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 in 1990s. Note that our bound is much larger than the conjectured optimal upper bound O(n^0.25) due to Peres.

The right angle here is “lifting canonical paths”.
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 (2004) on holographic algorithms, is among the most expressive ones. One way to formulate the Holant is to evaluate the contraction of a given tensor network. In the two papers listed above, we establish complete classifications in both the general and planar settings, for the symmetric constraint functions (or tensors).

The right angle here is “the vanishing signatures”.

Misc

Yitong Yin and I organised a (much belated) NII Shonan seminar MCMC 2.0 (Sep 4-7, 2023) in Shonan, Japan. See here for more details.
Jingcheng Liu and I organised a STOC 2020 workshop “New frontiers of approximate counting”. See here for more details.
I no longer organize the LFCS seminar series. The organizer after me is Ohad Kammar.
Apparently, you are welcome to count in Edinburgh.
(Picture shot on W Nicolson St.)
In my spare time, I enjoy video and board games a lot. In some distant past, I even play competitively. (See e.g. here and here.)