Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2015 | public
Book Section - Chapter

Symbolic Integration and the Complexity of Computing Averages


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 the anti-ferromagnetic settings), the average size of an independent set in the hard core model, and the average size of a matching in the monomer-dimer model. We prove that for all non-trivial values of the underlying model parameters, exactly computing these averages is #P-hard. In contrast to previous results of Sinclair and Srivastava [1] for the mean magnetization of the ferromagnetic Ising model, our approach does not use any Lee-Yang type theorems about the complex zeros of partition functions. Indeed, it was due to the lack of suitable Lee-Yang theorems for models such as the anti-ferromagnetic Ising model that some of the problems we study here were left open in [1]. In this paper, we instead use some relatively simple and well-known ideas from the theory of automatic symbolic integration to complete our hardness reductions.

Additional Information

© 2015 IEEE. We thank an anonymous referee for observing that an appeal to the polynomial factoring algorithm of Lenstra, Lenstra and Lovász is not necessary in the proof of our main technical lemma. LJS and PS were supported in part by NSF grant CCF-1319745. AS was supported by in part by NSF grant CCF-1420934 and the Simons Institute for the Theory of Computing.

Additional details

August 22, 2023
January 13, 2024