Approximate Counting for Spin Systems in Sub-Quadratic Time
- Dr. Jiaheng Wang, University of Edinburgh
- Time: 2023-09-19 16:00
- Host: Dr. Yuqing Kong
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
We present two approximate counting algorithms with O(n^(2-c)/ε^2) running time for some constant c>0 and accuracy ε:
(1) for the hard-core model when strong spatial mixing (SSM) is sufficiently fast;
(2) for spin systems with SSM on planar graphs with quadratic growth, such as Z^2.
The latter algorithm also extends to (not necessarily planar) graphs with polynomial growth, such as Z^d, albeit with a running time of O(n^2/superpolylog(n)). Our technique utilizes Weitz's self-avoiding walk tree (STOC, 2006) and the recent marginal sampler of Anand and Jerrum (SIAM J. Comput., 2022).
Joint work with Konrad Anand (Queen Mary), Weiming Feng (UC Berkeley), Graham Freifeld (Edinburgh) and Heng Guo (Edinburgh). Available at arXiv:2306.14867.
Biography
Jiaheng Wang is currently a Postdoctoral Research Associate (PDRA) at the School of Informatics, University of Edinburgh. He obtained a PhD degree at the same university under the supervision of Heng Guo. Prior to that, he got a BSc degree at Peking University and was a member of the first Turing Class. He has a general interest in algorithms and complexity, with a focus on approximate counting problems.