Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
We consider the algorithmic problem of computing the partition function of the Sherrington-Kirkpatrick model of spin glasses with Gaussian couplings. We show that there is no polynomial time algorithm for computing the partition function exactly (in the sense to be made precise), unless P=\#P. Our proof uses the Lipton's reducibility trick of computation modulo large primes~\cite{lipton1991new} and near-uniformity of the log-normal distribution in small intervals. To the best of our knowledge, this is the first statistical physics model with random parameters for which such average case hardness is established.
NurtureToken New!

Token crowdsale for this paper ends in

Buy Nurture Tokens

Author

Are you an author of this paper? Check the Twitter handle we have for you is correct.

David Gamarnik (add twitter)
Category

Mathematics - Probability

Subcategories
-
Ask The Authors

Ask the authors of this paper a question or leave a comment.

Read it. Rate it.
#1. Which part of the paper did you read?

#2. The paper contains new data or analyses that is openly accessible?
#3. The conclusion is supported by the data and analyses?
#4. The conclusion is of scientific interest?
#5. The result is likely to lead to future research?

Github
User:
None (add)
Repo:
None (add)
Stargazers:
0
Forks:
0
Open Issues:
0
Network:
0
Subscribers:
0
Language:
None
Youtube
Link:
None (add)
Views:
0
Likes:
0
Dislikes:
0
Favorites:
0
Comments:
0
Other
Sample Sizes (N=):
Inserted:
Words Total:
Words Unique:
Source:
Abstract:
None
10/15/18 07:07PM
4,592
1,177
Tweets
MathPaper: Computing the partition function of the Sherrington-Kirkpatrick model is hard on average. https://t.co/8MLB4zI5CL
Images
Related