Speaker:
Weiming Feng(research associate in University of Edinburgh)
Time:
- 11:00-12:00 (Time in Beijing)
- 15:00-16:00 (Time in Auckland)
- September 17, 2021 (Friday)
Venue:
B1-518B, Research Building 4
Abstract:
We prove an optimal lower bound on spectral gap of the Glauber dynamics for anti-ferromagnetic two-spin systems with vertices in the tree uniqueness regime. This spectral gap holds for all, including unbounded, maximum degree. Applications include mixing time for hardcore model and mixing time for Ising model.
Technique wise, we introduce a new notion called the complete spectral independence, and use a novel Markov chain called the field dynamics to connect complete spectral independence to the rapid mixing of Glauber dynamics for all degrees.
The talk is based on joint the work with Xiaoyu Chen, Yitong Yin and Xinyuan Zhang. The paper will appear in FOCS 2021.
Speaker Bio:
Weiming Feng (凤维明) will be a research associate (postdoc) in School of Informatics, University of Edinburgh. He obtained his Ph.D. degree from Nanjing University in June 2021, advised by Professor Yitong Yin. He obtained B.Eng. degree from UESTC in June 2016. His research interest lies in theoretical computer science. Currently, he focuses on sampling and counting algorithms.