Premium
Fast algorithms at low temperatures via Markov chains †
Author(s) -
Chen Zongchen,
Galanis Andreas,
Goldberg Leslie A.,
Perkins Will,
Stewart James,
Vigoda Eric
Publication year - 2021
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20968
Subject(s) - glauber , potts model , markov chain , expander graph , ising model , degree (music) , mixing (physics) , polynomial , bipartite graph , exponent , markov chain mixing time , sampling (signal processing) , bounded function , mathematics , statistical physics , algorithm , discrete mathematics , computer science , markov model , balance equation , physics , mathematical analysis , philosophy , filter (signal processing) , graph , linguistics , acoustics , optics , quantum mechanics , scattering , computer vision , statistics
Efficient algorithms for approximate counting and sampling in spin systems typically apply in the so‐called high‐temperature regime, where the interaction between neighboring spins is “weak.” Instead, recent work of Jenssen, Keevash, and Perkins yields polynomial‐time algorithms in the low‐temperature regime on bounded‐degree (bipartite) expander graphs using polymer models and the cluster expansion. In order to speed up these algorithms (so the exponent in the run time does not depend on the degree bound) we present a Markov chain for polymer models and show that it is rapidly mixing under exponential decay of polymer weights. This yields, for example, an O ( n log n ) ‐time sampling algorithm for the low‐temperature ferromagnetic Potts model on bounded‐degree expander graphs. Combining our results for the hard‐core and Potts models with Markov chain comparison tools, we obtain polynomial mixing time for Glauber dynamics restricted to appropriate portions of the state space.