LFCS Seminar: Tuesday 7 October: Zongchen Chen

Title: New Rapid Mixing Results for the Hardcore Model

Abstract: Over the past decades, a fascinating computational phase transition has been identified in sampling weighted independent sets from the hardcore model. However, the computational complexity at the critical point remains poorly understood, as previous algorithmic and hardness results all required a constant slack from this threshold. In this talk, I will introduce our recent result on resolving this open question at the critical threshold, thus completing the picture of the computational phase transition. Specifically, we show that for the critical hardcore model, the mixing time of Glauber dynamics is always polynomial and in the worst case super-linear in the number of vertices. Furthermore, we establish that on random regular graphs, rapid mixing holds far beyond the uniqueness threshold, showing that the worst-case and average-case complexities of sampling from the hardcore model are fundamentally different. Based on joint work with Xiaoyu Chen, Zejia Chen, Tianhui Jiang, Yitong Yin, and Xinyuan Zhang.