We are pleased to report that alumnus Heng Guo (PhD ’15) has been awarded the European Association for Theoretical Computer Science (EATCS) Distinguished Dissertation Award 2016. Guo was advised by Dr. Jin-Yi Cai.
Guo's research focuses on the computational complexity of counting problems. Counting problems include the computation of all kinds of quantities such as the number of satisfying assignments, proper graph colorings, success probabilities, and partition functions in statistical physics, etc. They have important applications all across computer science. Heng Guo endeavors to map out the landscape of counting problems according to their inherent difficulty. In particular, he has shown sweeping dichotomy theorems regarding constraint satisfaction problems and Boolean Holant problems, both on general graphs and on planar graphs. In addition, he has made contributions to advance approximate counting/sampling algorithms, improving techniques such as correlation decay and Markov chain Monte Carlo algorithms.