Disordered systems insights on computational hardness

Cites Work

Spectral redemption in clustering sparse networks
Sparse Bayesian Methods for Low-Rank Matrix Estimation
Reducibility among combinatorial problems
Global optimization with polynomials and the problem of moments
Title not available (Why is that?)
A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
Sum-of-squares proofs and the quest toward optimal algorithms
Analysis of Boolean Functions
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
The complexity of theorem-proving procedures
The thermodynamic limit in mean field spin glass models
The Parisi ultrametricity conjecture
The Parisi formula
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
The Sherrington-Kirkpatrick model
Anneaux preordonnes
Optimal shrinkage of eigenvalues in the spiked covariance model
Title not available (Why is that?)
The nature of computation
On a positive semidefinite relaxation of the cut polytope
On the solution-space geometry of random constraint satisfaction problems
Limits of local algorithms over sparse random graphs
Universality in polytope phase transitions and message passing algorithms
Sparse sums of squares on finite abelian groups and improved semidefinite lifts
The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
A Theory of Cooperative Phenomena
On the solution-space geometry of random constraint satisfaction problems
An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
Title not available (Why is that?)
Statistical Physics of Spin Glasses and Information Processing
State evolution for general approximate message passing algorithms, with applications to spatial coupling
An approach to obtaining global extremums in polynomial mathematical programming problems
Application of statistical mechanics to NP-complete problems in combinatorial optimisation
A Limit Theorem for Multidimensional Galton-Watson Processes
Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
Survey propagation: An algorithm for satisfiability
Determining computational complexity from characteristic ``phase transitions
Rounding sum-of-squares relaxations
Quiet planting in the locked constraint satisfaction problems
Semidefinite programs on sparse random graphs and their application to community detection
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
Title not available (Why is that?)
Lower bounds for subgraph isomorphism
Complexity of Positivstellensatz proofs for the knapsack
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
Disorder chaos in some diluted spin Glass models
On the energy landscape of spherical spin glasses
Strongly refuting random CSPs below the spectral threshold
SOS is not obviously automatizable, even approximately
Title not available (Why is that?)
Suboptimality of local algorithms for a class of max-cut problems
Sum-of-squares certificates for maxima of random tensors on the sphere
Optimization of mean-field spin glasses
Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
On the bit complexity of sum-of-squares proofs
On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
The overlap gap property and approximate message passing algorithms for \(p\)-spin models
Optimal errors and phase transitions in high-dimensional generalized linear models
A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
Lifting sum-of-squares lower bounds: degree-2 to degree-4
HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
The Lovász theta function for random regular graphs and community detection in the hard regime
Storage capacity in symmetric binary perceptrons
Frozen 1-RSB structure of the symmetric Ising perceptron
Approximate survey propagation for statistical inference

Cited In (4)

Statistical mechanics of the maximum-average submatrix problem
Counting and hardness-of-finding fixed points in cellular automata on random graphs
Average-case complexity of tensor decomposition for low-degree polynomials
On the free energy of vector spin glasses with nonconvex interactions

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

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