CaltechAUTHORS
  A Caltech Library Service

Zeros of ferromagnetic 2-spin systems

Guo, Heng and Liu, Jingcheng and Lu, Pinyan (2020) Zeros of ferromagnetic 2-spin systems. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA, pp. 181-192. ISBN 978-1-61197-599-4. https://resolver.caltech.edu/CaltechAUTHORS:20200828-121031001

[img] PDF - Published Version
See Usage Policy.

881Kb
[img] PDF - Submitted Version
See Usage Policy.

677Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200828-121031001

Abstract

We study zeros of the partition functions of ferromagnetic 2-state spin systems in terms of the external field, and obtain new zero-free regions of these systems via a refinement of Asano's and Ruelle's contraction method. The strength of our results is that they do not depend on the maximum degree of the underlying graph. Via Barvinok's method, we also obtain new efficient and deterministic approximate counting algorithms. When the edge interaction is attractive for both spins, our algorithm outperforms all other methods such as Markov chain Monte Carlo and correlation decay.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/1.9781611975994.11DOIArticle
https://arxiv.org/abs/1907.06156arXivDiscussion Paper
Additional Information:© 2020 by SIAM. We would like to thank the organisers of the workshop “Deterministic Counting, Probability, and Zeros of Partition Functions" in the Simons Institute for the Theory of Computing. The topic of the workshop inspired us to look at this problem and the work was initiated during the workshop. We thank anonymous reviewers for helpful comments on an early version of the paper. HG wants to thank the hospitality of the Institute of Theoretical Computer Science in Shanghai University of Finance and Economics, where part of the work was done. JL was a PhD student at UC Berkeley when this work was carried out, and was supported by US NSF grant CCF-1815328. PL is supported by NSFC grant 61922052 and 61932002, Innovation Program of Shanghai Municipal Education Commission, Program for Innovative Research Team of Shanghai University of Finance and Economics, and the Fundamental Research Funds for the Central Universities.
Funders:
Funding AgencyGrant Number
NSFCCF-1815328
National Natural Science Foundation of China61922052
National Natural Science Foundation of China61932002
Shanghai Municipal Education CommissionUNSPECIFIED
Shanghai UniversityUNSPECIFIED
Fundamental Research Funds for the Central UniversitiesUNSPECIFIED
Record Number:CaltechAUTHORS:20200828-121031001
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200828-121031001
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105142
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:28 Aug 2020 21:26
Last Modified:28 Aug 2020 21:26

Repository Staff Only: item control page