Disordered systems insights on computational hardness (Q5055432): Difference between revisions

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