Lee-Yang theorems and the complexity of computing averages

DOI10.1145/2488608.2488686MaRDI QIDQ5495833zbMATH OpenOpenAlexFDO

Authors Alistair Sinclair, Piyush Srivastava

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.2376

zbMATH Keywords

counting problemsIsing modelLee-Yang theoremmonomer-dimer model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

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.

Recommendations

• Lee-Yang theorems and the complexity of computing averages
• The computational complexity of two‐state spin systems
• The Ising partition function: zeros and deterministic approximation
• Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
• The Complexity of Ferromagnetic Ising with Local Fields

Cited in

(7)

• Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
• Lee-Yang theorems and the complexity of computing averages
• A logician's view of graph polynomials
• Semantic equivalence of graph polynomials definable in second order logic
• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Two-state spin systems with negative interactions
• Two-state spin systems with negative interactions

This page was built for publication: Lee-Yang theorems and the complexity of computing averages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495833)