Optimization of mean-field spin glasses

DOI10.1214/21-AOP1519MaRDI QIDQ2072085zbMATH OpenFDO

Authors 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

optimization algorithmsspin glassesfinding ground statesthe Parisi formula

Mathematics Subject Classification ID

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

Recommendations

• Optimizing mean field spin glasses with external field
• Optimization algorithms for multi-species spherical spin glasses
• Recent results on the energy landscapes of mean field spin glasses
• Optimization on sparse random hypergraphs and spin glasses
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models

Cites work

• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 1751767 (Why is no real title available?)
• A dynamic programming approach to the Parisi functional
• A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• Approximate ground states of hypercube spin glasses are near corners
• Course 7 Computing the number of metastable states in infinite-range models
• Determining computational complexity from characteristic ``phase transitions
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Gradient descent dynamics in the mixed \(p\)-spin spherical model: finite-size simulations and comparison with mean-field integration
• Hypercontractivity, sum-of-squares proofs, and their applications
• Information, Physics, and Computation
• Lifting sum-of-squares lower bounds: degree-2 to degree-4
• Limits of local algorithms over sparse random graphs
• On the energy landscape of the mixed even \(p\)-spin model
• On the out-of-equilibrium relaxation of the Sherrington-Kirkpatrick model
• Parisi formula for the ground state energy in the mixed \(p\)-spin model
• Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem
• Random matrices and complexity of spin glasses
• State evolution for approximate message passing with non-separable functions
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Suboptimality of local algorithms for a class of max-cut problems
• Sum-of-squares certificates for maxima of random tensors on the sphere
• The Aizenman-Sims-Starr scheme and Parisi formula for mixed \(p\)-spin spherical models
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• The Parisi formula
• The Parisi formula has a unique minimizer
• The Parisi ultrametricity conjecture
• The Sherrington-Kirkpatrick model
• The algorithmic hardness threshold for continuous random energy models
• The best rank-1 approximation of a symmetric tensor and related spherical optimization problems
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Universality in polytope phase transitions and message passing algorithms

Cited in

(21)

• Optimal low-degree hardness of maximum independent set
• Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
• Approximate message passing algorithms for rotationally invariant matrices
• Statistical mechanics analysis of generalized multi-dimensional knapsack problems
• On weak ergodicity breaking in mean-field spin glasses
• Shattering versus metastability in spin glasses
• Spin glasses and nonlinear constraints in portfolio optimization
• 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
• The threshold energy of low temperature Langevin dynamics for pure spherical spin glasses
• Tight Lipschitz hardness for optimizing mean field spin glasses
• Algorithmic pure states for the negative spherical perceptron
• Optimization of Mean-field Spin Glasses
• Disordered systems insights on computational hardness
• Generalized TAP Free Energy
• Approximate ground states of hypercube spin glasses are near corners
• On the free energy of vector spin glasses with nonconvex interactions
• Optimization algorithms for multi-species spherical spin glasses
• A review on quantum approximate optimization algorithm and its variants
• Optimizing mean field spin glasses with external field

This page was built for publication: Optimization of mean-field spin glasses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2072085)