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
- Zeros of Holant problems: locations and algorithms
with Chao Liao, Pinyan Lu, and Chihao Zhang
SODA 2019 [ PDF | arXiv ] - Approximately counting bases of bicircular matroids
with Mark Jerrum
submitted [ PDF | arXiv ] - Tight bounds for popping algorithms
with Kun He
submitted [ PDF | arXiv ] - 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 ] - A polynomial-time approximation algorithm for all-terminal network reliability
with Mark Jerrum
ICALP 2018 (Best paper award for track A) [ PDF | arXiv | slides ] - Perfect simulation of the hard disks model by partial rejection sampling
with Mark Jerrum
ICALP 2018 [ PDF | arXiv ] - Counting hypergraph colorings in the local lemma regime
with Chao Liao, Pinyan Lu, and Chihao Zhang
STOC 2018 [ PDF | arXiv | slides ] - 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 ] - Uniform sampling through the Lovász local lemma
with Mark Jerrum and Jingcheng Liu
STOC 2017 [ PDF | arXiv | slides ] - Approximation via correlation decay when strong spatial mixing fails
with Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič
ICALP 2016 [ 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 ] - A Holant dichotomy: Is the FKT algorithm universal?
with Jin-Yi Cai, Zhiguo Fu, and Tyson Williams
FOCS 2015 [ 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 ] - The complexity of planar Boolean #CSP with complex weights
with Tyson Williams
ICALP 2013 [ PDF | arXiv | slides ] - 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 ]