Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy

Given a random n-variate degree-d homogeneous polynomial f , we study the following problem:

• Publication year

  2016

• Venue

  arXiv.org

• Publication date

  2016-05-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1605.00903
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Strongly refuting random CSPs below the spectral threshold

  2016cited by this paper
• Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms

  2015cited by this paper
• Tensor principal component analysis via sum-of-square proofs

  2015cited by this paper
• Convergence analysis for Lasserre’s measure-based hierarchy of upper bounds for polynomial optimization

  2014cited by this paper
• Spectral norm of random tensors

  2014cited by this paper
• A statistical model for tensor PCA

  2014cited by this paper
• Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method

  2014cited by this paper
• Rounding sum-of-squares relaxations

  2013cited by this paper
• Hypercontractivity, sum-of-squares proofs, and their applications

  2012cited by this paper
• Convergence of SDP hierarchies for polynomial optimization on the hypersphere

  2012cited by this paper
• Quantum de Finetti Theorems Under Local Measurements with Applications

  2012cited by this paper
• Introduction to the non-asymptotic analysis of random matrices

  2010cited by this paper
• Random Tensors and Planted Cliques

  2009cited by this paper
• A new approach to the planted clique problem

  2008cited by this paper
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey

  2008cited by this paper
• Random walk in a simplex and quadratic optimization over convex polytopes

  2003cited by this paper
• Clique Is Hard To Approximate Within

  2000cited by this paper
• Finding and certifying a large hidden clique in a semirandom graph

  2000cited by this paper
• Clique is hard to approximate withinn1−ε

  1999cited by this paper
• The Classical Moment Problem as a Self-Adjoint Finite Difference Operator

  1998cited by this paper

• Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio

  2019cites this paper
• The Kikuchi Hierarchy and Tensor PCA

  2019cites this paper
• Statistical Inference and the Sum of Squares Method

  2018cites this paper
• Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares

  2017cites this paper
• The Power of Sum-of-Squares for Detecting Hidden Structures

  2017cites this paper
• Exact tensor completion with sum-of-squares

  2017cites this paper
• The Landscape of the Spiked Tensor Model

  2017cites this paper
• Random Matrices and the Sum-of-Squares Hierarchy

  2017cites this paper
• Strongly refuting random CSPs below the spectral threshold

  2016cites this paper
• Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere

  2016cites this paper
• Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere

  2016cites this paper
• Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere

  2016cites this paper