Technical Program

Paper Detail

Paper IDT.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

Visit Website!