2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | T.1.2 | ||
| Paper Title | Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average | ||
| Authors | David Gamarnik, Eren C. Kizildag, MIT, United States | ||
| Session | T.1: Complexity and Computation Theory | ||
| Presentation | Lecture | ||
| Track | Topics in Information Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | We establish the average-case hardness of the algorithmic problem of exactly computing the partition function of the Sherrington-Kirkpatrick model of spin glasses with Gaussian couplings. In particular, we establish that unless $P= \#P$, there does not exist a polynomial-time algorithm to exactly compute this object on average. This is done by showing that if there exists a polynomial-time algorithm exactly computing the partition function for a certain fraction of all inputs, then there is a polynomial-time algorithm exactly computing this object for all inputs, with high probability, yielding $P=\#P$. Our results cover both finite-precision arithmetic as well as the real-valued computational models. The ingredients of our proofs include Berlekamp-Welch algorithm, a list-decoding algorithm by Sudan for reconstructing a polynomial from its noisy samples, near-uniformity of log-normal distribution modulo a large prime; and a control over total variation distance for log-normal distribution under convex perturbation. To the best of our knowledge, this is the first average-case hardness result pertaining a statistical physics model with random parameters. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
