The algorithmic hardness threshold for continuous random energy models

DOI10.4171/MSL/12zbMath1434.68182arXiv1810.05129OpenAlexW3007832888MaRDI QIDQ2176074

Pascal Maillard, Louigi Addario-Berry

Publication date: 4 May 2020

Published in: Mathematical Statistics and Learning (Search for Journal in Brave)

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

zbMATH Keywords

Gaussian processcombinatorial optimizationrandom energy modelspin glassalgorithmic lower boundalgorithmic hardness

Mathematics Subject Classification ID

Gaussian processes (60G15) Combinatorial optimization (90C27) 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Efficient approximation of branching random walk Gibbs measures, Algorithmic pure states for the negative spherical perceptron, The overlap gap property and approximate message passing algorithms for \(p\)-spin models, Optimization of the Sherrington--Kirkpatrick Hamiltonian, A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian, The overlap gap property in principal submatrix recovery, Optimization of mean-field spin glasses, Optimal low-degree hardness of maximum independent set

Cites Work

• Unnamed Item
• Unnamed Item
• Maximal displacement of a branching random walk in time-inhomogeneous environment
• Search cost for a nearly optimal path in a binary tree
• Postulates for subadditive processes
• The first birth problem for an age-dependent branching process
• Derrida's generalized random energy models. II: Models with continuous hierarchies
• Suboptimality of local algorithms for a class of max-cut problems
• Approximate Ultrametricity for Random Measures and Applications to Spin Glasses
• Belief Propagation Guided Decimation Fails on Random Formulas
• Random-energy model: An exactly solvable model of disordered systems
• The first- and last-birth problems for a multitype age-dependent branching process
• The Sherrington-Kirkpatrick Model
• Random Matrices and Complexity of Spin Glasses
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• On belief propagation guided decimation for random k-SAT
• Gibbs states and the set of solutions of random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• Mean Field Models for Spin Glasses
• Mean Field Models for Spin Glasses
• Brownian Motion