Name
Abstract | ||
|---|---|---|
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 (2013) 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 by Sinclair and Srivastava. 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/FOCS.2015.79 | IEEE Symposium on Foundations of Computer Science |
Keywords | Field | DocType |
Computational Complexity,Statistical Mechanics,Counting Problems,#P-hardness | Discrete mathematics,Statistical mechanics,Symbolic integration,Combinatorics,Partition function (mathematics),Core model,Counting problem,Independent set,Ising model,Mathematics,Computational complexity theory | Conference |
ISSN | Citations | PageRank |
0272-5428 | 0 | 0.34 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Leonard J. Schulman | 1 | 1328 | 136.88 |
| Alistair Sinclair | 2 | 1506 | 308.40 |
| Piyush Srivastava | 3 | 65 | 4.55 |