Disordered systems insights on computational hardness

DOI10.1088/1742-5468/ac9cc8OpenAlexW4309896457MaRDI QIDQ5055432

David Gamarnik, Lenka Zdeborová, Moore, Cristopher

Publication date: 13 December 2022

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

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

zbMATH Keywords

statistical inferencemessage-passing algorithmscavity and replica methodtypical-case computational complexity

Mathematics Subject Classification ID

Statistical mechanics, structure of matter (82-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• On the energy landscape of spherical spin glasses
• Disorder chaos in some diluted spin Glass models
• The thermodynamic limit in mean field spin glass models
• On a positive semidefinite relaxation of the cut polytope
• The Parisi ultrametricity conjecture
• Optimization of mean-field spin glasses
• 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
• Universality in polytope phase transitions and message passing algorithms
• Anneaux preordonnes
• Optimal shrinkage of eigenvalues in the spiked covariance model
• Suboptimality of local algorithms for a class of max-cut problems
• The Parisi formula
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Global Optimization with Polynomials and the Problem of Moments
• Spectral redemption in clustering sparse networks
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• An approach to obtaining global extremums in polynomial mathematical programming problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Sparse Bayesian Methods for Low-Rank Matrix Estimation
• Sum-of-squares proofs and the quest toward optimal algorithms
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• SOS Is Not Obviously Automatizable, Even Approximately
• Statistical Physics of Spin Glasses and Information Processing
• The Sherrington-Kirkpatrick Model
• Strongly refuting random CSPs below the spectral threshold
• Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
• Reducibility among Combinatorial Problems
• Approximate survey propagation for statistical inference
• Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
• Storage capacity in symmetric binary perceptrons
• On the Bit Complexity of Sum-of-Squares Proofs
• HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
• LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM
• Lifting sum-of-squares lower bounds: degree-2 to degree-4
• Analysis of Boolean Functions
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Optimal errors and phase transitions in high-dimensional generalized linear models
• The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
• Rounding sum-of-squares relaxations
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Survey propagation: An algorithm for satisfiability
• Determining computational complexity from characteristic ‘phase transitions’
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Semidefinite programs on sparse random graphs and their application to community detection
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• A Limit Theorem for Multidimensional Galton-Watson Processes
• The complexity of theorem-proving procedures
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• On the $AC^0$ Complexity of Subgraph Isomorphism
• A Theory of Cooperative Phenomena
• On the solution-space geometry of random constraint satisfaction problems
• On the solution‐space geometry of random constraint satisfaction problems
• Limits of local algorithms over sparse random graphs
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Complexity of Positivstellensatz proofs for the knapsack
• Frozen 1-RSB structure of the symmetric Ising perceptron

This page was built for publication: Disordered systems insights on computational hardness