The overlap gap property and approximate message passing algorithms for \(p\)-spin models

DOI10.1214/20-AOP1448zbMath1470.60277arXiv1911.06943MaRDI QIDQ2227713

David Gamarnik, Aukosh Jagannath

Publication date: 15 February 2021

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

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

zbMATH Keywords

spin glassesapproximate message passingoverlap gap property

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (14)

Approximate message passing algorithms for rotationally invariant matrices ⋮ Disordered systems insights on computational hardness ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Efficient approximation of branching random walk Gibbs measures ⋮ Generalized TAP Free Energy ⋮ Free Energy Wells and Overlap Gap Property in Sparse PCA ⋮ Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Optimizing mean field spin glasses with external field ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ Approximate ground states of hypercube spin glasses are near corners ⋮ On convergence of the cavity and Bolthausen's TAP iterations to the local magnetization ⋮ Optimization of mean-field spin glasses ⋮ Optimal low-degree hardness of maximum independent set

Cites Work

• Unnamed Item
• Unnamed Item
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• Some properties of the phase diagram for mixed \(p\)-spin glasses
• Low temperature asymptotics of spherical mean field spin glasses
• Algorithmic thresholds for tensor PCA
• Free energy of the spherical mean field model
• On the energy landscape of the mixed even \(p\)-spin model
• Spectral gap estimates in mean field spin glasses
• The geometry of the Gibbs measure of pure spherical spin glasses
• Finding a large submatrix of a Gaussian random matrix
• Local algorithms for independent sets are half-optimal
• The algorithmic hardness threshold for continuous random energy models
• Bounding flows for spherical spin glass dynamics
• Universality in polytope phase transitions and message passing algorithms
• On properties of Parisi measures
• Suboptimality of local algorithms for a class of max-cut problems
• A dynamic programming approach to the Parisi functional
• Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
• On independent sets in random graphs
• Bounds on the complexity of Replica Symmetry Breaking for spherical spin glasses
• The Sherrington-Kirkpatrick Model
• State evolution for approximate message passing with non-separable functions
• The SK Model Is Infinite Step Replica Symmetry Breaking at Zero Temperature
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Walksat Stalls Well Below Satisfiability
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Random Fields and Geometry
• A CDMA multiuser detection algorithm on the basis of belief propagation
• On the solution‐space geometry of random constraint satisfaction problems
• Limits of local algorithms over sparse random graphs

This page was built for publication: The overlap gap property and approximate message passing algorithms for \(p\)-spin models