2012/11/11 by Alistair Sinclair, Sinclair, Alistair, Piyush Srivastava +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.2 #FOS: Computer and information sciences #FOS: Physical sciences #G.2.1 #Markov Chains and Monte Carlo Methods #Statistical Mechanics (cond-mat.stat-mech)
paper · pdf · doi:10.48550/arxiv.1211.2376
openalex publication_date 2012/11/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.