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

DOI10.1214/20-AAP1625zbMath1474.68161arXiv1810.05907OpenAlexW3175234097MaRDI QIDQ2240857

Eren C. Kızıldağ, David Gamarnik

Publication date: 4 November 2021

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.05907

zbMATH Keywords

computational complexitypartition functionspin glassesstatistical physicsSherrington-Kirkpatrick modellist decodingaverage-case hardness

Mathematics Subject Classification ID

Combinatorial probability (60C05) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Algorithmic obstructions in the random number partitioning problem ⋮ An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization

Cites Work

• Highly resilient correctors for polynomials
• Notes on computational-to-statistical gaps: predictions using statistical physics
• Statistical mechanics, three-dimensionality and NP-completeness
• The Sherrington-Kirkpatrick Model
• Optimization of the Sherrington--Kirkpatrick Hamiltonian
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• The computational complexity of linear optics
• Information Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computing the partition function of the Sherrington-Kirkpatrick model is hard on average