Disordered systems insights on computational hardness
From MaRDI portal
Recommendations
- Statistical mechanics methods and phase transitions in optimization problems
- Random instances of problems in NP -- algorithms and statistical physics
- Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
- scientific article; zbMATH DE number 67483
- Computational complexity, phase transitions, and message-passing for community detection
Cites work
- A Limit Theorem for Multidimensional Galton-Watson Processes
- A nearly tight sum-of-squares lower bound for the planted clique problem
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- A Theory of Cooperative Phenomena
- A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
- An approach to obtaining global extremums in polynomial mathematical programming problems
- An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
- Analysis of Boolean Functions
- Anneaux preordonnes
- Application of statistical mechanics to NP-complete problems in combinatorial optimisation
- Approximate survey propagation for statistical inference
- Complexity of Positivstellensatz proofs for the knapsack
- Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
- Determining computational complexity from characteristic ``phase transitions
- Disorder chaos in some diluted spin Glass models
- Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
- Following the Ground States of <scp>Full‐RSB</scp> Spherical Spin Glasses
- Frozen 1-RSB structure of the symmetric Ising perceptron
- Global optimization with polynomials and the problem of moments
- HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
- scientific article; zbMATH DE number 67483 (Why is no real title available?)
- scientific article; zbMATH DE number 1273988 (Why is no real title available?)
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 5485586 (Why is no real title available?)
- scientific article; zbMATH DE number 7650426 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
- Lifting sum-of-squares lower bounds: degree-2 to degree-4
- Limits of local algorithms over sparse random graphs
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Lower bounds for subgraph isomorphism
- On a positive semidefinite relaxation of the cut polytope
- On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
- On the bit complexity of sum-of-squares proofs
- On the energy landscape of spherical spin glasses
- On the solution-space geometry of random constraint satisfaction problems
- On the solution-space geometry of random constraint satisfaction problems
- Optimal errors and phase transitions in high-dimensional generalized linear models
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Optimal shrinkage of eigenvalues in the spiked covariance model
- Optimization of mean-field spin glasses
- Quiet planting in the locked constraint satisfaction problems
- Reducibility among combinatorial problems
- Rounding sum-of-squares relaxations
- Semidefinite programs on sparse random graphs and their application to community detection
- SOS is not obviously automatizable, even approximately
- Sparse Bayesian Methods for Low-Rank Matrix Estimation
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Spectral redemption in clustering sparse networks
- State evolution for general approximate message passing algorithms, with applications to spatial coupling
- Statistical Physics of Spin Glasses and Information Processing
- Storage capacity in symmetric binary perceptrons
- Strongly refuting random CSPs below the spectral threshold
- Suboptimality of local algorithms for a class of max-cut problems
- Sum-of-squares certificates for maxima of random tensors on the sphere
- Sum-of-squares proofs and the quest toward optimal algorithms
- Survey propagation: An algorithm for satisfiability
- The complexity of theorem-proving procedures
- The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
- The Lovász theta function for random regular graphs and community detection in the hard regime
- The nature of computation
- The overlap gap property and approximate message passing algorithms for \(p\)-spin models
- The Parisi formula
- The Parisi ultrametricity conjecture
- The Sherrington-Kirkpatrick model
- The thermodynamic limit in mean field spin glass models
- Universality in polytope phase transitions and message passing algorithms
Cited in
(15)- Disordered Systems Insights on Computational Hardness
- Average-case complexity of tensor decomposition for low-degree polynomials
- Statistical mechanics of the maximum-average submatrix problem
- Counting and hardness-of-finding fixed points in cellular automata on random graphs
- On the free energy of vector spin glasses with nonconvex interactions
- Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
- Un-inverting the Parisi formula
- Shattering in the Ising p-spin glass model
- Bounds on the ground state energy of quantum p-spin Hamiltonians
- Precise error rates for computationally efficient testing
- The algorithmic phase transition of random graph alignment problem
- Faster algorithms for the alignment of sparse correlated Erdős-Rényi random graphs
- The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
- On the MCMC performance in Bernoulli group testing and the random max-set cover problem
- Sharp phase transitions for the overlap gap property
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)
