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

DOI10.1137/22M150263XarXiv2004.12063MaRDI QIDQ6203476FDOQ6203476

Aukosh Jagannath, Alexander S. Wein, David Gamarnik

Publication date: 28 February 2024

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

Abstract: We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions. Two concrete problems we consider are (a) optimizing the Hamiltonian of a spherical or Ising $p$-spin glass model, and (b) finding a large independent set in a sparse ErdH{o}s-R'{e}nyi graph. The following families of algorithms are considered: (a) low-degree polynomials of the input; (b) low-depth Boolean circuits; (c) the Langevin dynamics algorithm. We show that these families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory (although we consider the search problem as opposed to the decision problem). Our proof uses the fact that these models are known to exhibit a variant of the overlap gap property (OGP) of near-optimal solutions. Specifically, for both models, every two solutions whose objectives are above a certain threshold are either close or far from each other. The crux of our proof is that the classes of algorithms we consider exhibit a form of stability. We show by an interpolation argument that stable algorithms cannot overcome the OGP barrier. The stability of Langevin dynamics is an immediate consequence of the well-posedness of stochastic differential equations. The stability of low-degree polynomials and Boolean circuits is established using tools from Gaussian and Boolean analysis -- namely hypercontractivity and total influence, as well as a novel lower bound for random walks avoiding certain subsets. In the case of Boolean circuits, the result also makes use of Linal-Mansour-Nisan's classical theorem. Our techniques apply more broadly to low influence functions and may apply more generally.

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

zbMATH Keywords

Boolean circuitsrandom graphsmaximum independent setspin glassesLangevin dynamicsaverage-case hardnessoverlap gap propertyrandom optimization problemslow-degree methods

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• The threshold energy of low temperature Langevin dynamics for pure spherical spin glasses

This page was built for publication: Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics

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