Computing the partition function of the Sherrington-Kirkpatrick model is hard on average

David Sherrington and Scott Kirkpatrick, Solvable model of a spin-glass , Physical review letters 35

1975

Earlier work this paper cites.

Francisco Barahona, On the computational complexity of Ising spin glass models , Journal of Physics A: Mathematical and General 15

1982

Earlier work this paper cites.

Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines , [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, IEEE, 1988, pp. 387–397

1988

Earlier work this paper cites.

Richard J Lipton, New directions in testing. , Distributed computing and cryptography 2

1989

Earlier work this paper cites.

Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions , STOC, vol. 91, Citeseer, 1991, pp. 32–42

1991

Earlier work this paper cites.

Uriel Feige and Carsten Lund, On the hardness of computing the permanent of random matrices , Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, ACM, 1992, pp. 643–654

1992

Earlier work this paper cites.

Peter Gemmell and Madhu Sudan, Highly resilient correctors for polynomials , Information processing letters 43

1992

Earlier work this paper cites.

Erich Kaltofen, Polynomial factorization 1987–1991 , Latin American Symposium on Theoretical Informatics, Springer, 1992, pp. 294–313

1992

Cited alongside, same era.

Madhu Sudan, Maximum likelihood decoding of Reed Solomon codes , Proceedings of 37th Conference on Foundations of Computer Science, IEEE, 1996, pp. 164–172

1996

Cited alongside, same era.

Jin-Yi Cai, Aduri Pavan, and D Sivakumar, On the hardness of permanent , Annual Symposium on Theoretical Aspects of Computer Science, Springer, 1999, pp. 90–99

1999

Cited alongside, same era.

Sorin Istrail, Statistical mechanics, three-dimensionality and NP-completeness: I. universality of intracatability for the partition function of the ising model across non-planar surfaces , STOC, 2000, pp. 87–96

2000

Cited alongside, same era.

Imre Csiszar and János Körner, Information theory: coding theorems for discrete memoryless systems , Cambridge University Press, 2011

2011

Later among the works it cites.

Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation , Springer Science & Business Media, 2012

2012

Later among the works it cites.

Dmitry Panchenko, The Sherrington-Kirkpatrick model , Springer Science & Business Media, 2013

2013

Later among the works it cites.

Yury Polyanskiy and Yihong Wu, Lecture notes on information theory , Lecture Notes for ECE563 (UIUC) and 6.441 (MIT) (2016), 2012–2016

2016

Later among the works it cites.

David Gamarnik, Computing the partition function of the Sherrington-Kirkpatrick model is hard on average , arXiv preprint arXiv:1810.05907 (2018)

Original

2018

Closest in time.