Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics

DOI10.1137/22m150263xarXiv2004.12063MaRDI QIDQ6203476

Aukosh Jagannath, Alexander S. Wein, David Gamarnik

Publication date: 28 February 2024

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

spin glassesrandom graphsLangevin dynamicsmaximum independent setBoolean circuitsaverage-case hardnessoverlap gap propertyrandom optimization problemslow-degree methods

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Diffusion processes and stochastic analysis on manifolds (58J65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parisi formula, disorder chaos and fluctuation for the ground state energy in the spherical mixed \(p\)-spin models
• Low temperature asymptotics of spherical mean field spin glasses
• Algorithmic thresholds for tensor PCA
• On the independence number of random graphs
• On the energy landscape of spherical spin glasses
• Spectral gap estimates in mean field spin glasses
• The thermodynamic limit in mean field spin glass models
• Local algorithms for independent sets are half-optimal
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• Optimization of mean-field spin glasses
• Optimal low-degree hardness of maximum independent set
• Computational barriers to estimation from low-degree polynomials
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Approximate ground states of hypercube spin glasses are near corners
• Bounding flows for spherical spin glass dynamics
• On the spectral gap of spherical spin glass dynamics
• The extremal process of critical points of the pure \(p\)-spin spherical spin Glass model
• Large independent sets in regular graphs of large girth
• Maximum independent sets on random regular graphs
• Suboptimality of local algorithms for a class of max-cut problems
• Cugliandolo-Kurchan equations for dynamics of spin-glasses
• Replica symmetry breaking and the nature of the spin glass phase
• Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
• Constant depth circuits, Fourier transform, and learnability
• On independent sets in random graphs
• Gaussian Hilbert Spaces
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• High-Dimensional Probability
• The Sherrington-Kirkpatrick Model
• Random Matrices and Complexity of Spin Glasses
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
• How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA
• HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
• LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM
• Analysis of Boolean Functions
• Dynamics of mean field spin glasses on short and long timescales
• Walksat Stalls Well Below Satisfiability
• Computational Complexity
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• On the $AC^0$ Complexity of Subgraph Isomorphism
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• On the solution-space geometry of random constraint satisfaction problems
• Limiting dynamics for spherical models of spin glasses at high temperature
• Limits of local algorithms over sparse random graphs
• Aging of spherical spin glasses