License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.41
URN: urn:nbn:de:0030-drops-112560
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11256/
Chen, Zongchen ;
Galanis, Andreas ;
Goldberg, Leslie Ann ;
Perkins, Will ;
Stewart, James ;
Vigoda, Eric
Fast Algorithms at Low Temperatures via Markov Chains
Abstract
For spin systems, such as the hard-core model on independent sets weighted by fugacity lambda>0, efficient algorithms for the associated approximate counting/sampling problems typically apply in the high-temperature region, corresponding to low fugacity. Recent work of Jenssen, Keevash and Perkins (2019) yields an FPTAS for approximating the partition function (and an efficient sampling algorithm) on bounded-degree (bipartite) expander graphs for the hard-core model at sufficiently high fugacity, and also the ferromagnetic Potts model at sufficiently low temperatures. Their method is based on using the cluster expansion to obtain a complex zero-free region for the partition function of a polymer model, and then approximating this partition function using the polynomial interpolation method of Barvinok. We present a simple discrete-time Markov chain for abstract polymer models, and present an elementary proof of rapid mixing of this new chain under sufficient decay of the polymer weights. Applying these general polymer results to the hard-core and ferromagnetic Potts models on bounded-degree (bipartite) expander graphs yields fast algorithms with running time O(n log n) for the Potts model and O(n^2 log n) for the hard-core model, in contrast to typical running times of n^{O(log Delta)} for algorithms based on Barvinok's polynomial interpolation method on graphs of maximum degree Delta. In addition, our approach via our polymer model Markov chain is conceptually simpler as it circumvents the zero-free analysis and the generalization to complex parameters. Finally, we combine our results for the hard-core and ferromagnetic Potts models with standard Markov chain comparison tools to obtain polynomial mixing time for the usual spin system Glauber dynamics restricted to even and odd or "red" dominant portions of the respective state spaces.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs:2019:11256,
author = {Zongchen Chen and Andreas Galanis and Leslie Ann Goldberg and Will Perkins and James Stewart and Eric Vigoda},
title = {{Fast Algorithms at Low Temperatures via Markov Chains}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {41:1--41:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11256},
URN = {urn:nbn:de:0030-drops-112560},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.41},
annote = {Keywords: Markov chains, approximate counting, Potts model, hard-core model, expander graphs}
}
|
Keywords: |
|
Markov chains, approximate counting, Potts model, hard-core model, expander graphs |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
17.09.2019 |
