Name
Abstract | ||
|---|---|---|
We study the complexity of computing average quantities related to spin systems, such as the and in the ferromagnetic Ising model, and the (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, and hence, under standard assumptions, computationally intractable. In the case of the Ising model, our approach requires us to prove an extension of the famous Lee–Yang Theorem from the 1950s. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2488608.2488686 | Communications in Mathematical Physics |
Keywords | DocType | Volume |
ferromagnetic ising model,average quantity,mean magnetization,ising model,lee-yang theorem,average dimer count,partition function,complex zero,average size,famous lee-yang theorem,monomer-dimer model,counting problems | Conference | abs/1211.2376 |
Issue | ISSN | Citations |
3 | 0010-3616 | 4 |
PageRank | References | Authors |
0.43 | 12 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alistair Sinclair | 1 | 1506 | 308.40 |
| Piyush Srivastava | 2 | 65 | 4.55 |