Approximate counting and sampling for spin systems
Speaker
Kuan Yang,University of Hamburg
Time
2020-08-21 10:00:00 ~ 2020-08-21 11:30:00
Location
Room 1319, Software Expert Building
Host
Chihao Zhang
Abstract
Over the past 30 years, the study of counting problems has become an interesting and important area in theoretical computer science.The framework of counting problems can capture a variety of applications in diverse fields, such as counting the number of graph colourings and homomorphisms in graph theory, computing probabilistic inference in graphical models and Bayesian networks, sampling from the Ising and Potts model in statistical physics.
Recently, my research interests primarily lie in the area of designing efficient approximation algorithms and proving hardness results for approximate counting and sampling for spin system models. It is believed that a so-called "uniqueness" condition plays a prominent role in the efficiency of algorithms for sampling from the Gibbs distribution. One of my work is to compute the uniqueness threshold for the well-known Potts model on regular trees of small degree. Another part of my research focuses on exploring approximation algorithms in the uniqueness region, such as the FPTAS for counting proper 4-colourings on cubic graphs and approximate sampling on random regular graphs. Moreover, I also considered the generalisation of spin systems on hypergraphs and approximate counting and sampling algorithms for these models, including the FPTAS for the hypergraph hardcore and Ising model (in uniqueness region) and the FPTAS for the random k-CNF model (beyond uniqueness region).
Bio
Kuan Yang is a postdoc researcher at University of Hamburg. In 2020, he graduated from and has been awarded a Ph.D. degree in computer science by University of Oxford, where he was supervised by Prof. Leslie Ann Goldberg and Prof. Andreas Galanis. In addition, he was a Clarendon Scholar at Oxford, and a member of St. Hugh's College.
Before coming to Oxford, he received his bachelor degree in computer science from Zhiyuan College at Shanghai Jiao Tong University.He is broadly interested in theoretical computer science, probability and combinatorics. Currently, he mainly works on approximate counting and sampling algorithms.