Fetching the paper…
Reading the bibliography…
We show that, if $\mathbf{W} \in \mathbb{R}^{N \times N}_{\mathsf{sym}}$ is drawn from the gaussian orthogonal ensemble, then with high probability the degree 4 sum-of-squares relaxation cannot certify an upper bound on the objective $N^{-1} \cdot \mathbf{x}^\top \mathbf{W} \mathbf{x}$ under the constraints $x_i^2 - 1 = 0$ (i.e.
Reducibility among combinatorial problems
Richard M Karp · 1972
Earlier work this paper cites.
Solvable model of a spin-glass
David Sherrington and Scott Kirkpatrick · 1975
Earlier work this paper cites.
Infinite number of order parameters for spin-glasses
Giorgio Parisi · 1979
Earlier work this paper cites.
Linear algebra and geometry
PK Suetin, Alexandra I Kostrikin, and Yu I Manin · 1989
Earlier work this paper cites.
A note on extreme correlation matrices
Chi-Kwong Li and Bit-Shun Tam · 1994
Earlier work this paper cites.
Adaptive estimation of a quadratic functional by model selection
Beatrice Laurent and Pascal Massart · 2000
Earlier work this paper cites.
Global optimization with polynomials and the problem of moments
Jean B Lasserre · 2001
Earlier work this paper cites.
The concentration of measure phenomenon
Michel Ledoux · 2001
Earlier work this paper cites.
Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope
Monique Laurent · 2003
Earlier work this paper cites.
The Parisi formula
Michel Talagrand · 2006
Earlier work this paper cites.
On the existence of equiangular tight frames
Mátyás A Sustik, Joel A Tropp, Inderjit S Dhillon, and Robert W Heath Jr · 2007
Earlier work this paper cites.
Multivariate normal approximation using exchangeable pairs
Sourav Chatterjee and Elizabeth Meckes · 2008
Earlier work this paper cites.
Real equiangular frames
Peter G Casazza, Dan Redmond, and Janet C Tremain · 2008
Earlier work this paper cites.
Invertibility of random matrices: norm of the inverse
Mark Rudelson · 2008
Earlier work this paper cites.
The Littlewood–Offord problem and invertibility of random matrices
Mark Rudelson and Roman Vershynin · 2008
Earlier work this paper cites.
Geometry of cuts and metrics
Michel Marie Deza and Monique Laurent · 2009
Cited alongside, same era.
Sums of squares, moment matrices and optimization over polynomials
Monique Laurent · 2009
Cited alongside, same era.
Spectral norm of products of random and deterministic matrices
Roman Vershynin · 2011
Cited alongside, same era.
Semidefinite optimization and convex algebraic geometry
Grigoriy Blekherman, Pablo A Parrilo, and Rekha R Thomas · 2012
Cited alongside, same era.
Probability in Banach spaces: isoperimetry and processes
Michel Ledoux and Michel Talagrand · 2013
Cited alongside, same era.
The Parisi ultrametricity conjecture
Dmitry Panchenko · 2013
Cited alongside, same era.
Efficient Bayesian estimation from few samples: community detection and related problems
Samuel B Hopkins and David Steurer · 2017
Later among the works it cites.
SOS is not obviously automatizable, even approximately
Ryan O’Donnell · 2017
Later among the works it cites.
On the bit complexity of sum-of-squares proofs
Prasad Raghavendra and Benjamin Weitz · 2017
Later among the works it cites.
The algorithmic hardness threshold for continuous random energy models
Louigi Addario-Berry and Pascal Maillard · 2018
Later among the works it cites.
A Gramian description of the degree 4 generalized elliptope
Afonso S Bandeira and Dmitriy Kunisky · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Dmitry Panchenko · 2013
Cited alongside, same era.
Sum-of-squares proofs and the quest toward optimal algorithms
Boaz Barak and David Steurer · 2014
Cited alongside, same era.
A statistical model for tensor PCA
Emile Richard and Andrea Montanari · 2014
Cited alongside, same era.
Tables of the existence of equiangular tight frames
Matthew Fickus and Dustin G Mixon · 2015
Cited alongside, same era.
Sparse sums of squares on finite abelian groups and improved semidefinite lifts
Hamza Fawzi, James Saunderson, and Pablo A Parrilo · 2016
Cited alongside, same era.
Sum-of-squares hierarchy lower bounds for symmetric formulations
Adam Kurpisz, Samuli Leppänen, and Monaldo Mastrolilli · 2016
Cited alongside, same era.
Samuel Hopkins · 2018
Later among the works it cites.
Following the ground-states of full-RSB spherical spin glasses
Eliran Subag · 2018
Later among the works it cites.
A nearly tight sum-of-squares lower bound for the planted clique problem
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin · 2019
Closest in time.
Sum-of-squares optimization and the sparsity structure of equiangular tight frames
Afonso S Bandeira and Dmitriy Kunisky · 2019
Closest in time.
Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
Vishesh Jain, Frederic Koehler, and Andrej Risteski · 2019
Closest in time.
Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira · 2019
Closest in time.
Optimization of the Sherrington-Kirkpatrick Hamiltonian
Andrea Montanari · 2019
Closest in time.
Lifting sum-of-squares lower bounds: degree-2 to degree-4
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu · 2019
Closest in time.
Computational hardness of certifying bounds on constrained PCA problems
Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein · 2020
Closest in time.