Optimization of mean-field spin glasses

DOI10.1214/21-AOP1519MaRDI QIDQ2072085

Yanyan Li

Publication date: 1 February 2022

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

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

zbMATH Keywords

spin glassesoptimization algorithmsfinding ground statesthe Parisi formula

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Dynamics of disordered systems (random Ising systems, etc.) in time-dependent statistical mechanics (82C44) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Approximate message passing algorithms for rotationally invariant matrices, Disordered systems insights on computational hardness, Algorithmic pure states for the negative spherical perceptron, Generalized TAP Free Energy, Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree, Optimization algorithms for multi-species spherical spin glasses, Shattering versus metastability in spin glasses, Optimizing mean field spin glasses with external field, Tractability from overparametrization: the example of the negative perceptron, On the TAP equations via the cavity approach in the generic mixed \(p\)-spin models, Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics, Approximate ground states of hypercube spin glasses are near corners, Statistical mechanics analysis of generalized multi-dimensional knapsack problems, Optimal low-degree hardness of maximum independent set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Aizenman-Sims-Starr scheme and Parisi formula for mixed \(p\)-spin spherical models
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• Parisi formula for the ground state energy in the mixed \(p\)-spin model
• On the energy landscape of the mixed even \(p\)-spin model
• The Parisi ultrametricity conjecture
• The algorithmic hardness threshold for continuous random energy models
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
• Approximate ground states of hypercube spin glasses are near corners
• The Parisi formula has a unique minimizer
• Universality in polytope phase transitions and message passing algorithms
• Suboptimality of local algorithms for a class of max-cut problems
• The Parisi formula
• A dynamic programming approach to the Parisi functional
• Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
• Course 7 Computing the number of metastable states in infinite-range models
• Information, Physics, and Computation
• On the out-of-equilibrium relaxation of the Sherrington-Kirkpatrick model
• The Sherrington-Kirkpatrick Model
• The Best Rank-1 Approximation of a Symmetric Tensor and Related Spherical Optimization Problems
• Random Matrices and Complexity of Spin Glasses
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
• State evolution for approximate message passing with non-separable functions
• Lifting sum-of-squares lower bounds: degree-2 to degree-4
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Determining computational complexity from characteristic ‘phase transitions’
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Hypercontractivity, sum-of-squares proofs, and their applications
• Gradient descent dynamics in the mixed p-spin spherical model: finite-size simulations and comparison with mean-field integration
• Limits of local algorithms over sparse random graphs