Heng Guo

Heng Guo is an Associate Professor in Algorithms and Complexity at the School of Informatics, University of Edinburgh. He leads the ERC starting grant project New Approaches to Counting and Sampling (NACS), which runs from 2021 to 2026. Previously, he has worked and studied at Berkeley, London, Madison, and Beijing. His research lies at the intersection of theoretical computer science, combinatorics, and statistical physics.

Guo's research focuses on algorithms from a complexity perspective, particularly computational counting and sampling. He is renowned for his work on the Lovász local lemma, Markov chain Monte Carlo methods, phase transitions in computational complexity, and complexity classifications. His approach often involves discovering unseen links between different areas of theoretical computer science. Key contributions include confirming a conjecture of Gorodezky and Pak through partial rejection sampling, establishing rapid mixing for Swendsen-Wang dynamics, and developing a polynomial-time approximation algorithm for all-terminal network reliability.

His publication record shows a strong trajectory of impactful research in top venues including FOCS, STOC, SODA, J. ACM, and SIAM Journal on Computing. His work on the all-terminal network reliability problem won the Best Paper Award at ICALP 2018.

Guo has organized several significant workshops including JerrumFest 2025, MCMC 2.0 (Shonan seminar), and a STOC 2020 workshop on new frontiers of approximate counting. These events highlight his leadership role in the theoretical computer science community.

• Best Paper Award at ICALP 2018
• EATCS Distinguished Dissertation Award 2016

Guo has advised several PhD students including Giorgos Mousa, Jiaheng Wang, and Graham Freifeld, and mentored postdocs such as Weiming Feng, Vishvajeet Nagargoje, and Konrad Anand. His ERC grant supports multiple research associates working on counting and sampling problems. He has taught courses including Computational Complexity, Randomness and Computation, and Algorithmic Game Theory at the University of Edinburgh.