郭 珩 (Heng Guo)
Research Interests
Broadly speaking, I am interested in theoretical computer science. I am especially thrilled to discover unseen links among different areas. To be more specific, here are some topics that I am looking at recently:
- Approximate counting and sampling
- Markov chains and their mixing times
- Complexity classification of Holant, CSP, and other related problems
- Phase transitions in computational complexity
Research Articles
External databases: arXiv, DBLP, Google Scholar
I find it hard to quantify the percentage of contribution from AI in my papers, so I simply separate out pre- and after- AI papers below. I find that AI can often output elegant and clever ideas, even if it is a mere combination of existing techniques. I feel that these results deserve some understanding and exposition, so I am trying my best to streamline and record them.
x% AI idea for x > 0
- Approximate counting of vertices of 0/1 polytopes: a stronger hardness result
with Mark Jerrum
Preprint [ PDF | arXiv ] - An Õ(n3)-time sampler for zero-field ferromagnetic Ising models
with Weiming Feng and Yiyao Zhang
Preprint [ PDF | arXiv on hold ] - Approximating spin systems on planar graphs
with Xinyuan Zhang
Preprint [ PDF | arXiv ] - Approximating two-terminal network reliability
with Weiming Feng and Yucheng Fu
Preprint [ PDF | arXiv ] - Linear time approximation of the TV distance between product distributions
with Konrad Anand and Alistair Benford
Submitted [ PDF | arXiv ] - Fast counting and sampling for ferromagnetic two-spin systems
with Weiming Feng and Yichun Yang
Submitted [ PDF | arXiv ]
0% AI idea
- Rapid mixing in positively weighted restricted Boltzmann machines
with Weiming Feng and Minji Yang
FOCS 2026 [ PDF | arXiv ] - Simulating Gaussian boson sampling on graphs in polynomial time
with Konrad Anand, Zongchen Chen, Mary Cryan, Graham Freifeld, Leslie Ann Goldberg, and Xinyuan Zhang
Submitted [ PDF | arXiv ] - Deterministic counting from coupling independence
with Xiaoyu Chen, Weiming Feng, Xinyuan Zhang, and Zongrui Zou
FOCS 2025 [ PDF | arXiv | slides ] - Sink-free orientations: a local sampler with applications
with Konrad Anand, Graham Freifeld, Chunyang Wang, and Jiaheng Wang
RANDOM 2025 [ PDF | arXiv ] - Towards derandomising Markov chain Monte Carlo
with Weiming Feng, Chunyang Wang, Jiaheng Wang, and Yitong Yin
SIAM J. Comput., 54(3), 775–813, 2025 (Preliminary version in FOCS 2023) [ doi | PDF | arXiv | slides ] - Rapid mixing of the flip chain over non-crossing spanning trees
with Konrad Anand, Weiming Feng, Graham Freifeld, Mark Jerrum, and Jiaheng Wang
SoCG 2025 [ PDF | arXiv ] - Approximate counting for spin systems in sub-quadratic time
with Konrad Anand, Weiming Feng, Graham Freifeld, and Jiaheng Wang
TheoretiCS, 4:3, 2025 (Preliminary version in ICALP 2024) [ doi | PDF | arXiv ] - Deterministic approximation for the volume of the truncated fractional matching polytope
with Vishvajeet N
ITCS 2025 [ PDF | arXiv ] - Fast sampling of satisfying assignments from random k-SAT with applications to connectivity
with Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos, Nitya Mani, and Ankur Moitra
SIAM J. Discrete Math., 38(4), 2750–2811, 2024 [ doi | PDF | arXiv ] - Near-linear time samplers for matroid independent sets with applications
with Xiaoyu Chen, Xinyuan Zhang, and Zongrui Zou
RANDOM 2024 [ PDF | arXiv ] - An FPRAS for two terminal reliability in directed acyclic graphs
with Weiming Feng
ICALP 2024 [ PDF | arXiv | slides ] - Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
with Weiming Feng and Jiaheng Wang
Inf. Comput., 294:105066, 2023 [ doi | PDF | arXiv ] - A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
with Weiming Feng, Mark Jerrum, and Jiaheng Wang
TheoretiCS, 2:8, 2023 (Preliminary version in SOSA 2023) [ doi | PDF | arXiv ] - Improving certified robustness via statistical learning with logical reasoning
with Zhuolin Yang, Zhikuan Zhao, Boxin Wang, Jiawei Zhang, Linyi Li, Hengzhi Pei, Bojan Karlaš, Ji Liu, Ce Zhang, and Bo Li
NeurIPS 2022 [ arXiv ] - Inapproximability of counting hypergraph colourings
with Andreas Galanis and Jiaheng Wang
ACM Trans. Comput. Theory, 14(3-4):10, 2023 [ doi | PDF | arXiv ] - Improved bounds for randomly colouring simple hypergraphs
with Weiming Feng and Jiaheng Wang
RANDOM 2022 [ PDF | arXiv ] - Counting vertices of integer polytopes defined by facets
with Mark Jerrum
Discrete Comput. Geom., 70(3), 975–990, 2023 [ doi | PDF | arXiv ] - Rapid mixing from spectral independence beyond the Boolean domain
with Weiming Feng, Yitong Yin, and Chihao Zhang
ACM Trans. Algorithms, 18(3):28, 2022 (Preliminary version in SODA 2021) [ doi | PDF | arXiv ] - Perfect sampling from spatial mixing
with Weiming Feng and Yitong Yin
Random Struct. Algorithms, 61(4), 678-709, 2022 [ doi | PDF | arXiv ] - Counting solutions to random CNF formulas
with Andreas Galanis, Leslie Ann Goldberg, and Kuan Yang
SIAM J. Comput., 50(6), 1701-1738, 2021 (Preliminary version in ICALP 2020) [ doi | PDF | arXiv ] - Fast sampling and counting k-SAT solutions in the local lemma regime
with Weiming Feng, Yitong Yin, and Chihao Zhang
J. ACM, 68(6):40, 2021 (Preliminary version in STOC 2020) [ doi | PDF | arXiv | slides] - FKT is not universal — A planar Holant dichotomy for symmetric constraints
with Jin-Yi Cai, Zhiguo Fu, and Tyson Williams
Theory Comput. Syst., 66, 143–308, 2022 (Preliminary version in FOCS 2015) [ doi | PDF | arXiv | slides ] - Local-to-global contraction in simplicial complexes
with Giorgos Mousa
Preprint [ PDF | arXiv ] - Zeros of Holant problems: locations and algorithms
with Chao Liao, Pinyan Lu, and Chihao Zhang
ACM Trans. Algorithms, 17(1):4, 2021 (Preliminary version in SODA 2019) [ doi | PDF | arXiv ] - Modified log-Sobolev inequalities for strongly log-concave distributions
with Mary Cryan and Giorgos Mousa
Ann. Probab., 49(1), 506-525, 2021 (Preliminary version in FOCS 2019) [ doi | PDF | arXiv | slides ] - Approximately counting bases of bicircular matroids
with Mark Jerrum
Combin. Probab. Comput., 30(1), 124-135, 2021 [ doi | PDF | arXiv ] - Tight bounds for popping algorithms
with Kun He
Random Struct. Algorithms, 57(2), 371-392, 2020 [ doi | PDF | arXiv ] - Zeros of ferromagnetic 2-spin systems
with Jingcheng Liu and Pinyan Lu
SODA 2020 [ PDF | arXiv ] - The complexity of planar Boolean #CSP with complex weights
with Tyson Williams
J. Comput. Syst. Sci., 107, 1-27, 2020 (Preliminary version in ICALP 2013) [ doi | PDF | arXiv | slides ] - Perfect simulation of the hard disks model by partial rejection sampling
with Mark Jerrum
Ann. Inst. Henri Poincaré Comb. Phys. Interact. 8(2), 159-177, 2021 (Preliminary version in ICALP 2018) [ doi | PDF | arXiv ] - Counting hypergraph colorings in the local lemma regime
with Chao Liao, Pinyan Lu, and Chihao Zhang
SIAM J. Comput., 48(4), 1397-1424, 2019 (Preliminary version in STOC 2018) [ doi | PDF | arXiv | slides ] - A polynomial-time approximation algorithm for all-terminal network reliability
with Mark Jerrum
SIAM J. Comput., 48(3), 964-978, 2019 (Preliminary version in ICALP 2018, Best Paper Award) [ doi | PDF | arXiv | slides ] - Approximation via correlation decay when strong spatial mixing fails
with Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič
SIAM J. Comput., 48(2), 279-349, 2019 (Preliminary version in ICALP 2016) [ doi | PDF | arXiv | slides ] - Uniform sampling through the Lovász local lemma
with Mark Jerrum and Jingcheng Liu
J. ACM, 66(3):18, 2019 (Preliminary version in STOC 2017) [ doi | PDF | arXiv | slides ] - Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems
with Pinyan Lu
ACM Trans. Comput. Theory, 10(4):17, 2018 (Preliminary version in RANDOM 2016) [ doi | PDF | arXiv | slides ] - Clifford gates in the Holant framework
with Jin-Yi Cai and Tyson Williams
Theor. Comput. Sci., 745, 163-171, 2018 [ doi | PDF | arXiv ] - Holographic algorithms beyond matchgates
with Jin-Yi Cai and Tyson Williams
Inf. Comput., 259(1), 102-129, 2018 (Preliminary version in ICALP 2014) [ doi | PDF | arXiv | slides ] - Layerwise systematic scan: deep Boltzmann machines and beyond
with Kaan Kara and Ce Zhang
AISTATS 2018 [ PMLR | PDF | arXiv ] - Random cluster dynamics for the Ising model is rapidly mixing
with Mark Jerrum
Ann. Appl. Probab., 28(2), 1292-1313, 2018 (Preliminary version in SODA 2017) [ doi | PDF | arXiv | slides ] - The complexity of approximating complex-valued Ising and Tutte partition functions
with Leslie Ann Goldberg
Comput. Complex., 26(4), 765-833, 2017 [ doi | PDF | arXiv | slides ] - 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 (Preliminary version in STOC 2013) [ doi | PDF | arXiv | slides ] - The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
with Jin-Yi Cai and Tyson Williams
Res. Math. Sci., 3:18, 2016 (Preliminary version in FOCS 2014) [ doi | PDF | arXiv | slides ] - #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree nonuniqueness region
with Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Daniel Štefankovič and Eric Vigoda
J. Comput. Syst. Sci., 82(5) 690-711, 2016 (Preliminary version in RANDOM 2014) [ doi | PDF | arXiv | slides ] - The complexity of symmetric Boolean parity Holant problems
with Pinyan Lu and Leslie G. Valiant
SIAM J. Comput., 42(1), 324-356, 2013 (Preliminary version in ICALP 2011) [ doi | PDF ] - Inapproximability after uniqueness phase transition in two-spin systems
with Jin-Yi Cai, Xi Chen, and Pinyan Lu
COCOA 2012 [ PDF | arXiv ] - The complexity of weighted Boolean #CSP modulo k
with Sangxia Huang, Pinyan Lu, and Mingji Xia
STACS 2011 [ PDF ] - On model checking Boolean BI
with Hanpin Wang, Zhongyuan Xu, and Yongzhi Cao
CSL 2009 [ PDF | slides ]
Dissertation
- Complexity classification of exact and approximate counting problems
Adviser: Prof. Jin-Yi Cai
University of Wisconsin - Madison, 2015
EATCS Distinguished Dissertation Award 2016 [ PDF ]
Book Chapters / Surveys
- On the complexity of Holant problems
Heng Guo and Pinyan Lu
The Constraint Satisfaction Problem, Dagstuhl Follow-Ups 7, 159–177, 2017 [ doi ] - Mapping the complexity of counting problems
Heng Guo
Bulletin of EATCS, No 120: October 2016 [ link | pdf ] - Holant problems
Jin-Yi Cai, Heng Guo, and Tyson Williams
Encyclopedia of Algorithms, 2016: 918-921 [ doi ]