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
Random Cluster Dynamics for the Ising Model is Rapidly Mixing
with Mark Jerrum
Ann. Appl. Probab. to appear (Preliminary version in SODA 2017) [ PDF | arXiv | slides ]Layerwise Systematic Scan: Deep Boltzmann Machines and Beyond
with Kaan Kara and Ce Zhang
submitted [ PDF | arXiv ]Clifford Gates in the Holant Framework
with Jin-Yi Cai and Tyson Williams
submitted [ PDF | arXiv ]The Complexity of Approximating Complex-Valued Ising and Tutte Partition Functions
with Leslie Ann Goldberg
Comput. Complex. 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 ]Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
with Pinyan Lu
RANDOM 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 ]Holographic Algorithms beyond Matchgates
with Jin-Yi Cai and Tyson Williams
ICALP 2014 [ 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 ]