Abstract:
In this talk, I will discuss the problem of sampling from the Potts model on random regular graphs. It is conjectured that sampling is possible when the temperature of the model is in the so-called tree uniqueness regime, where the Gibbs distribution of the d-ary regular tree is unique. For all integers q>=3 and d>=3, we develop algorithms that produce samples within error o(1) from the q-state Potts model on random d-regular graphs, whenever the temperature is in uniqueness, for both the ferromagnetic and antiferromagnetic cases. While the precise uniqueness threshold on the tree is still not known for general q and d in the antiferromagnetic case, our algorithm works throughout uniqueness regardless of its value. In the case of the ferromagnetic Potts model, we are able to simplify the algorithm significantly by utilizing the random-cluster representation of the model.
Based on joint works with Antonio Blanca, Andreas Galanis, Leslie Goldberg, Daniel Štefankovič and Eric Vigoda.
Biography:
Kuan Yang is an assistant professor in John Hopcroft Center for Computer Science at Shanghai Jiao Tong University. He was awarded the Ph.D. degree in Computer Science by the University of Oxford in 2020. Before coming to Oxford, he obtained the bachelor degree in Computer Science from Zhiyuan College at Shanghai Jiao Tong University.
Kuan Yang is broadly interested in theoretical computer science. Currently his research focus on approximate counting and sampling algorithms.
Seminar by the NYU-ECNU Institute of Mathematical Sciences at NYU Shanghai