CS Theory Colloquium Series
Fall 2023
|
Monday, November 6th, 3:30pm, Harold Frank Hall (HFH) room 1132 Speaker: Xiaoyu Chen (Nanjing) Title: Uniqueness and Rapid Mixing in the Bipartite Hardcore Model Abstract: Counting the number of independent sets in a bipartite graph (#BIS) is a central open problem in approximate counting. Its weighted variant is known as the bipartite hardcore model. In this work, we study the bipartite hardcore model in the high-temperature regime. We show a uniqueness threshold for bipartite graphs that has almost the same form as the tree uniqueness threshold for general graphs, except with degree bounds only on one side of the bipartition. Moreover, under this uniqueness threshold, we are able to give a nearly linear time sampling algorithm and show that the standard Glauber dynamics mix in polynomial time. Bio: Xiaoyu Chen is currently a fourth-year Ph.D. student in the Department of Computer Science and Technology at Nanjing University, where he is in the CS Theory Group. He is fortunate to be advised by Professor Yitong Yin. His primary area of interest lies in theoretical computer science, with a current research focus on Markov chain Monte Carlo (MCMC) methods, which have extensive applications in approximate sampling and counting. |