Fetching the paper…
Reading the bibliography…
The degree-$4$ Sum-of-Squares (SoS) SDP relaxation is a powerful algorithm that captures the best known polynomial time algorithms for a broad range of problems including MaxCut, Sparsest Cut, all MaxCSPs and tensor PCA.
Infinite Number of Order Parameters for Spin-Glasses
G. Parisi · 1979
Earlier work this paper cites.
A sequence of approximated solutions to the S-K model for spin glasses
Giovanni P. Parisi · 1980
Earlier work this paper cites.
Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications
M. Mezard, G. Parisi, and M. Virasoro · 1987
Earlier work this paper cites.
Class of global minimum bounds of polynomial functions
N. Z. Shor · 1987
Earlier work this paper cites.
Models of random regular graphs
Nicholas C Wormald · 1999
Earlier work this paper cites.
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
Pablo A Parrilo · 2000
Earlier work this paper cites.
Statistical Mechanics of Learning
Andreas Engel and Christian P. L. Van den Broeck · 2001
Earlier work this paper cites.
Complexity of positivstellensatz proofs for the knapsack
Dima Grigoriev · 2001
Earlier work this paper cites.
Linear lower bound on degrees of positivstellensatz calculus proofs for the parity
Dima Grigoriev · 2001
Earlier work this paper cites.
Global optimization with polynomials and the problem of moments
Jean B Lasserre · 2001
Earlier work this paper cites.
Statistical Physics of Spin Glasses and Information Processing: an Introduction
Hidetoshi Nishimori · 2001
Earlier work this paper cites.
Analytic and Algorithmic Solution of Random Satisfiability Problems
M. Mézard, G. Parisi, and R. Zecchina · 2002
Earlier work this paper cites.
A proof of alon’s second eigenvalue conjecture
Joel Friedman · 2003
Earlier work this paper cites.
The Parisi formula
Michel Talagrand · 2006
Earlier work this paper cites.
Non-backtracking random walks mix faster
Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin · 2007
Cited alongside, same era.
Linear level Lasserre lower bounds for certain k-CSPs
Grant Schoenebeck · 2008
Cited alongside, same era.
Information, Physics, and Computation
Marc Mezard and Andrea Montanari · 2009
Cited alongside, same era.
CSP Gaps and Reductions in the Lasserre Hierarchy
Madhur Tulsiani · 2009
Cited alongside, same era.
Introduction to the non-asymptotic analysis of random matrices, 2010
Roman Vershynin · 2010
Cited alongside, same era.
Universality of wigner random matrices: a survey of recent results
Laszlo Erdős · 2011
Cited alongside, same era.
Extremal cuts of sparse random graphs
Amir Dembo, Andrea Montanari, Subhabrata Sen, et al · 2017
Later among the works it cites.
The power of sum-of-squares for detecting hidden structures
Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer · 2017
Later among the works it cites.
Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems
Samuel B. Hopkins and David Steurer · 2017
Later among the works it cites.
Sum of Squares Lower Bounds for Refuting Any CSP
Pravesh K. Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer · 2017
Later among the works it cites.
Strongly refuting random csps below the spectral threshold
Prasad Raghavendra, Satish Rao, and Tselil Schramm · 2017
Later among the works it cites.
Reducibility and computational lower bounds for problems with planted sparse structure
Matthew Brennan, Guy Bresler, and Wasim Huleihel · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Quentin Berthet and Philippe Rigollet · 2013
Cited alongside, same era.
Invariant gaussian processes and independent sets on regular graphs of large girth
Endre Csóka, Balázs Gerencsér, Viktor Harangi, and Bálint Virág · 2015
Cited alongside, same era.
Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems
Yash Deshpande and Andrea Montanari · 2015
Cited alongside, same era.
The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into ℓ 1
Subhash A Khot and Nisheeth K Vishnoi · 2015
Cited alongside, same era.
A nearly tight sum-of-squares lower bound for the planted clique problem
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin · 2016
Cited alongside, same era.
Semidefinite programs on sparse random graphs and their application to community detection
Andrea Montanari and Subhabrata Sen · 2016
Cited alongside, same era.
Later among the works it cites.
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, and Tselil Schramm · 2018
Later among the works it cites.
Optimization of the Sherrington-Kirkpatrick Hamiltonian
Andrea Montanari · 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.
A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts
Charles Bordenave · 2019
Closest in time.
The threshold for sdp-refutation of random regular nae-3sat
Yash Deshpande, Andrea Montanari, Ryan O’Donnell, Tselil Schramm, and Subhabrata Sen · 2019
Closest in time.
A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
Dmitriy Kunisky and Afonso S Bandeira · 2019
Closest in time.
Extended formulation lower bounds for refuting random csps
Jonah Issac-Brown Cohen and Prasad Raghavendra · 2020
Closest in time.