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.MFCS.2020.36
URN: urn:nbn:de:0030-drops-127038
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12703/
Galanis, Andreas ;
Goldberg, Leslie Ann ;
Herrera-Poyatos, Andrés
The Complexity of Approximating the Complex-Valued Potts Model
Abstract
We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane.
Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q ≥ 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations.
BibTeX - Entry
@InProceedings{galanis_et_al:LIPIcs:2020:12703,
author = {Andreas Galanis and Leslie Ann Goldberg and Andr{\'e}s Herrera-Poyatos},
title = {{The Complexity of Approximating the Complex-Valued Potts Model}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {36:1--36:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12703},
URN = {urn:nbn:de:0030-drops-127038},
doi = {10.4230/LIPIcs.MFCS.2020.36},
annote = {Keywords: approximate counting, Potts model, Tutte polynomial, partition function, complex numbers}
}
|
Keywords: |
|
approximate counting, Potts model, Tutte polynomial, partition function, complex numbers |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
