Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average
© 2020 IEEE. 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 e...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144132 |
| _version_ | 1826208942541242368 |
|---|---|
| author | Gamarnik, David Kizildag, Eren C |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Gamarnik, David Kizildag, Eren C |
| author_sort | Gamarnik, David |
| collection | MIT |
| description | © 2020 IEEE. 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. |
| first_indexed | 2024-09-23T14:15:11Z |
| format | Article |
| id | mit-1721.1/144132 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:15:11Z |
| publishDate | 2022 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1441322023-06-12T18:09:10Z Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average Gamarnik, David Kizildag, Eren C Sloan School of Management Massachusetts Institute of Technology. Institute for Data, Systems, and Society Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © 2020 IEEE. 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. 2022-07-29T16:21:12Z 2022-07-29T16:21:12Z 2020 2022-07-29T16:11:34Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/144132 Gamarnik, David and Kizildag, Eren C. 2020. "Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average." IEEE International Symposium on Information Theory - Proceedings, 2020-June. en 10.1109/ISIT44484.2020.9174373 IEEE International Symposium on Information Theory - Proceedings Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Gamarnik, David Kizildag, Eren C Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average |
| title | Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average |
| title_full | Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average |
| title_fullStr | Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average |
| title_full_unstemmed | Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average |
| title_short | Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average |
| title_sort | computing the partition function of the sherrington kirkpatrick model is hard on average |
| url | https://hdl.handle.net/1721.1/144132 |
| work_keys_str_mv | AT gamarnikdavid computingthepartitionfunctionofthesherringtonkirkpatrickmodelishardonaverage AT kizildagerenc computingthepartitionfunctionofthesherringtonkirkpatrickmodelishardonaverage |