Fetching the paper…
Reading the bibliography…
We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x \in \mathbb{R}^n$ that maximizes $|f(x)|$.
Block diagonally dominant matrices and generalizations of the gerschgorin circle theorem
David G Feingold, Richard S Varga, et al · 1962
Earlier work this paper cites.
Clique is hard to approximate within n 1-&epsiv
Johan Håstad · 1996
Earlier work this paper cites.
Deterministic and randomized polynomial-time approximation of radii
Andreas Brieden, Peter Gritzmann, Ravindran Kannan, Victor Klee, László Lovász, and Miklós Simonovits · 2001
Earlier work this paper cites.
A large deviation result on the number of small subgraphs of a random graph
Van H Vu · 2001
Earlier work this paper cites.
Random walk in a simplex and quadratic optimization over convex polytopes
Yurii Nesterov · 2003
Earlier work this paper cites.
On the advantage over a random assignment
Johan Håstad and Srinivasan Venkatesh · 2004
Earlier work this paper cites.
Upper tails for subgraph counts in random graphs
Svante Janson, Krzysztof Oleszkiewicz, and Andrzej Ruciński · 2004
Earlier work this paper cites.
Divide and conquer martingales and the number of triangles in a random graph
Jeong Han Kim and Van H Vu · 2004
Earlier work this paper cites.
A PTAS for the minimization of polynomials of fixed degree over the simplex
Etienne de Klerk, Monique Laurent, and Pablo A Parrilo · 2006
Earlier work this paper cites.
The complexity of optimizing over a simplex, hypercube or sphere: a short survey
Etienne De Klerk · 2008
Earlier work this paper cites.
A new approach to the planted clique problem
Alan Frieze and Ravi Kannan · 2008
Earlier work this paper cites.
Linear equations modulo 2 and the l_1 diameter of convex bodies
Subhash Khot and Assaf Naor · 2008
Earlier work this paper cites.
Random tensors and planted cliques
S Charles Brubaker and Santosh S Vempala · 2009
Earlier work this paper cites.
Moments, positive polynomials and their applications
Jean Bernard Lasserre · 2009
Earlier work this paper cites.
Sums of squares, moment matrices and optimization over polynomials
Monique Laurent · 2009
Cited alongside, same era.
Approximation algorithms for homogeneous polynomial optimization with quadratic constraints
Simai He, Zhening Li, and Shuzhong Zhang · 2010
Cited alongside, same era.
Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems
Anthony Man-Cho So · 2011
Cited alongside, same era.
Hypercontractivity, sum-of-squares proofs, and their applications
Boaz Barak, Fernando GSL Brandao, Aram W Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou · 2012
Cited alongside, same era.
The missing log in large deviations for triangle counts
Sourav Chatterjee · 2012
Cited alongside, same era.
Upper tails for triangles
Bobby DeMarco and Jeff Kahn · 2012
A statistical model for tensor PCA
Andrea Montanari and Emile Richard · 2014
Later among the works it cites.
Estimating operator norms using covering nets
Fernando GSL Brandao and Aram W Harrow · 2015
Later among the works it cites.
Dictionary learning and tensor decomposition via the sum-of-squares method
Boaz Barak, Jonathan A Kelner, and David Steurer · 2015
Later among the works it cites.
An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
Etienne de Klerk, Monique Laurent, and Zhao Sun · 2015
Later among the works it cites.
Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems
Yash Deshpande and Andrea Montanari · 2015
Later among the works it cites.
Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Tight upper tail bounds for cliques
Robert DeMarco and Jeff Kahn · 2012
Cited alongside, same era.
Decoupling: from dependence to independence
Victor De la Pena and Evarist Giné · 2012
Cited alongside, same era.
Convergence of sdp hierarchies for polynomial optimization on the hypersphere
Andrew C Doherty and Stephanie Wehner · 2012
Cited alongside, same era.
Quantum de finetti theorems under local measurements with applications
Fernando GSL Brandao and Aram W Harrow · 2013
Cited alongside, same era.
Approximability and proof complexity
Ryan O’Donnell and Yuan Zhou · 2013
Cited alongside, same era.
Rounding sum-of-squares relaxations
Boaz Barak, Jonathan A Kelner, and David Steurer · 2014
Cited alongside, same era.
Rong Ge and Tengyu Ma · 2015
Later among the works it cites.
Tensor principal component analysis via sum-of-square proofs
Samuel B Hopkins, Jonathan Shi, and David Steurer · 2015
Later among the works it cites.
Certifying random polynomials over the unit sphere via sum of squares hierarchy
Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee · 2016
Closest in time.
A nearly tight sum-of-squares lower bound for the planted clique problem
Boaz Barak, Samuel B Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin · 2016
Closest in time.
On the variational problem for upper tails in sparse random graphs
Eyal Lubetzky and Yufei Zhao · 2016
Closest in time.
Strongly refuting random csps below the spectral threshold
Prasad Raghavendra, Satish Rao, and Tselil Schramm · 2016
Closest in time.
Quantum entanglement, sum of squares, and the log rank conjecture
Boaz Barak, Pravesh Kothari, and David Steurer · 2017
Closest in time.
Personal communication
Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer · 2017
Closest in time.
Sum of squares lower bounds for refuting any csp
Pravesh K Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer · 2017
Closest in time.