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

	PDF - Published Version See Usage Policy. 902kB
	PDF - Submitted Version See Usage Policy. 693kB

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:

URL	URL Type	Description
https://doi.org/10.1137/1.9781611975994.11	DOI	Article
https://arxiv.org/abs/1907.06156	arXiv	Discussion 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 Agency	Grant Number
NSF	CCF-1815328
National Natural Science Foundation of China	61922052
National Natural Science Foundation of China	61932002
Shanghai Municipal Education Commission	UNSPECIFIED
Shanghai University	UNSPECIFIED
Fundamental Research Funds for the Central Universities	UNSPECIFIED

DOI:

10.1137/1.9781611975994.11

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:

16 Nov 2021 18:40

Repository Staff Only: item control page