research-article

Lee-Yang theorems and the complexity of computing averages

Authors:

Alistair Sinclair,

Piyush SrivastavaAuthors Info & Claims

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

Pages 625 - 634

https://doi.org/10.1145/2488608.2488686

Published: 01 June 2013 Publication History

Abstract

We study the complexity of computing average quantities related to spin systems, such as the mean magnetization and susceptibility in the ferromagnetic Ising model, and the average dimer count (or average size of a matching) in the monomer-dimer model. By establishing connections between the complexity of computing these averages and the location of the complex zeros of the partition function, we show that these averages are #P-hard to compute. In case of the Ising model, our approach requires us to prove an extension of the famous Lee-Yang Theorem from the 1950s.

References

[1]

S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

Digital Library

[2]

T. Asano. Lee-Yang theorem and the Griffiths inequality for the anisotropic Heisenberg ferromagnet. Phys. Rev. Lett., 24(25):1409--1411, 1970.

[3]

M. Biskup, Feb. 2012. Personal communication.

[4]

M. Biskup, C. Borgs, J. Chayes, L. Kleinwaks, and R. Kotecký. Partition function zeros at first-order phase transitions: A general analysis. Comm. Math. Phys., 251(1):79--131, 2004.

[5]

M. Biskup, C. Borgs, J. Chayes, and R. Kotecký. Partition function zeros at first-order phase transitions: Pirogov-Sinai theory. J. Stat. Phys., 116(1):97--155, 2004.

[6]

J. Borcea and P. Brandén. The Lee-Yang and Pólya-Schur programs. I. Linear operators preserving stability. Invent. Math., 177(3):541--569, 2009.

[7]

J. Borcea and P. Brandén. Pólya-Schur master theorems for circular domains and their boundaries. Ann. Math., 170(1):465--492, 2009.

[8]

O. Brune. Synthesis of a finite two-terminal network whose driving-point impedance is a prescribed function of frequency. Sc. D. Thesis, MIT, 1931.

[9]

A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53:66--120, 2006.

Digital Library

[10]

A. Bulatov and M. Grohe. The complexity of partition functions. Theoret. Comput. Sci., 348(2--3):148--186, 2005.

Digital Library

[11]

J.-Y. Cai and X. Chen. Complexity of counting CSP with complex weights. In STOC '12, pp. 909--920. ACM, 2012.

Digital Library

[12]

Y.-B. Choe, J. G. Oxley, A. D. Sokal, and D. G. Wagner. Homogeneous multivariate polynomials with the half-plane property. Adv. in Appl. Math., 32(1--2):88--187, 2004.

[13]

M. Chudnovsky and P. Seymour. The roots of the independence polynomial of a clawfree graph. J. Combin. Theory Ser. B, 97(3):350--357, 2007.

Digital Library

[14]

R. Clark. The Routh-Hurwitz stability criterion, revisited. IEEE Control Systems, 12(3):119--120, 1992.

[15]

M. E. Dyer and C. S. Greenhill. The complexity of counting graph homomorphisms. Random Structures Algorithms, 17(3--4):260--289, 2000.

Digital Library

[16]

J. Edmonds. Systems of distinct representatitives and linear algebra. J. Res. Nat. Bur. Stand. Sect. B, 71B(4):241--245, 1967.

[17]

L. A. Goldberg, M. Grohe, M. Jerrum, and M. Thurley. A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput., 39(7):3336--3402, 2010.

Digital Library

[18]

R. B. Griffiths. Correlations in Ising ferromagnets. I. J. Math. Phys., 8(3):478--483, 1967.

[19]

O. J. Heilmann and E. H. Lieb. Theory of monomer-dimer systems. Comm. Math. Phys., 25(3):190--232, 1972.

[20]

M. Jerrum, L. G. Valiant, and V. V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci., 43:169--188, 1986.

[21]

E. Laguerre. Sur les fonctions du genre zéro et du genre un. C. R. Acad. Sci., 98, 1882.

[22]

T. D. Lee and C. N. Yang. Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model. Phys. Rev., 87(3):410--419, 1952.

[23]

N. Macon and D. E. Dupree. Existence and uniqueness of interpolating rational functions. Amer. Math. Monthly, 69(8):751--759, 1962.

[24]

C. M. Newman. Zeros of the partition function for generalized Ising systems. Comm. Pure Appl. Math., 27(2):143--159, 1974.

[25]

C. M. Newman. The GHS inequality and the Riemann hypothesis. Constr. Approx., 7(1):389--399, 1991.

[26]

C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

[27]

G. Pólya and I. Schur. Über zwei Arten von Faktorenfolgen in der Theorie der Algebraischen Gleichungen. J. Reine Angew. Math., 144:89--113, 1914.

[28]

D. Ruelle. Statistical Mechanics. W. A. Benjamin, 1983.

[29]

A. Sinclair and P. Srivastava. Lee-Yang theorems and the complexity of computing averages. CoRR, abs/1211.2376, 2012. Full version of this paper.

[30]

A. Sly. Computational transition at the uniqueness threshold. In FOCS '10, pp. 287--296. IEEE, 2010.

Digital Library

[31]

A. Sly and N. Sun. The computational hardness of counting in two-spin models on d-regular graphs. In FOCS '12, pp. 361--369. IEEE, 2012.

Digital Library

[32]

M. Suzuki and M. E. Fisher. Zeros of the partition function for the Heisenberg, ferroelectric, and general Ising models. J. Math. Phys., 12(2):235--246, 1971.

[33]

L. G. Valiant. The complexity of computing the permanent. Theoret. Comput. Sci., 8:189--201, 1979.

[34]

L. G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410--421, 1979.

Digital Library

[35]

D. Weitz. Counting independent sets up to the tree threshold. In STOC '06, pp. 140--149. ACM, 2006.

Digital Library

[36]

C. N. Yang and T. D. Lee. Statistical theory of equations of state and phase transitions. I. Theory of condensation. Phys. Rev., 87(3):404--409, 1952.

Cited By

Makowsky JRavve EKotek T(2019)A Logician's View of Graph PolynomialsAnnals of Pure and Applied Logic10.1016/j.apal.2019.04.007Online publication date: Apr-2019
https://doi.org/10.1016/j.apal.2019.04.007
Anari NGharan SSaberi ASrivastava NCzumaj A(2018)Approximating the largest root and applications to interlacing familiesProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175336(1015-1028)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175336
Makowsky JRavve E(2016)Semantic Equivalence of Graph Polynomials Definable in Second Order LogicProceedings of the 23rd International Workshop on Logic, Language, Information, and Computation - Volume 980310.1007/978-3-662-52921-8_18(279-296)Online publication date: 16-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-662-52921-8_18
Show More Cited By

Index Terms

Lee-Yang theorems and the complexity of computing averages
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Enumeration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Symbolic Integration and the Complexity of Computing Averages
FOCS '15: Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)

We study the computational complexity of several natural problems arising in statistical physics and combinatorics. In particular, we consider the following problems: the mean magnetization and mean energy of the Ising model (both the ferromagnetic and ...
Exploring the renormalization of quantum discord and Bell non-locality in the one-dimensional transverse Ising model

In this paper, the effect of external magnet field g on the relationship among the quantum discord, Bell non-locality and quantum phase transition by employing quantum renormalization-group (QRG) method in the one-dimensional transverse Ising model is ...
The Complexity of Approximating complex-valued Ising and Tutte partition functions

We study the complexity of approximately evaluating the Ising and Tutte partition functions with complex parameters. Our results are partly motivated by the study of the quantum complexity classes BQP and IQP. Recent results show how to encode quantum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

June 2013

998 pages

ISBN:9781450320290

DOI:10.1145/2488608

General Chairs:
Dan Boneh
Stanford University, USA
,
Tim Roughgarden
Stanford University, USA
,
Program Chair:
Joan Feigenbaum
Yale University, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'13

Sponsor:

SIGACT

STOC'13: Symposium on Theory of Computing

June 1 - 4, 2013

California, Palo Alto, USA

Acceptance Rates

STOC '13 Paper Acceptance Rate 100 of 360 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
145
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Makowsky JRavve EKotek T(2019)A Logician's View of Graph PolynomialsAnnals of Pure and Applied Logic10.1016/j.apal.2019.04.007Online publication date: Apr-2019
https://doi.org/10.1016/j.apal.2019.04.007
Anari NGharan SSaberi ASrivastava NCzumaj A(2018)Approximating the largest root and applications to interlacing familiesProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175336(1015-1028)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175336
Makowsky JRavve E(2016)Semantic Equivalence of Graph Polynomials Definable in Second Order LogicProceedings of the 23rd International Workshop on Logic, Language, Information, and Computation - Volume 980310.1007/978-3-662-52921-8_18(279-296)Online publication date: 16-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-662-52921-8_18
Schulman LSinclair ASrivastava P(2015)Symbolic Integration and the Complexity of Computing AveragesProceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2015.79(1231-1245)Online publication date: 17-Oct-2015
https://dl.acm.org/doi/10.1109/FOCS.2015.79
Lelarge MZhou H(2013)Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree GraphsAlgorithms and Computation10.1007/978-3-642-45030-3_14(141-151)Online publication date: 2013
https://doi.org/10.1007/978-3-642-45030-3_14

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents