Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere

No abstract is available for this paper.

• Publication year

  2016

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2016-11-18

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2017.97
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Power of Sum-of-Squares for Detecting Hidden Structures

  2017cited by this paper
• Quantum entanglement, sum of squares, and the log rank conjecture

  2017cited by this paper
• Sum of squares lower bounds for refuting any CSP

  2017cited by this paper
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

  2016cited by this paper
• Decoupling From Dependence To Independence

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

  2016cited by this paper
• Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy

  2016cited by this paper
• Strongly refuting random CSPs below the spectral threshold

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

  2016cited by this paper
• Estimating operator norms using covering nets

  2015influential reference
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems

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

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

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

  2014cited by this paper
• On the variational problem for upper tails in sparse random graphs

  2014cited by this paper
• Sum-of-squares proofs and the quest toward optimal algorithms

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

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

  2014cited by this paper
• An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex

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

  2013cited by this paper
• Proceedings of the forty-fifth annual ACM symposium on Theory of computing

  2013cited by this paper
• Approximability and proof complexity

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

  2012cited by this paper
• Proceedings of the forty-fourth annual ACM symposium on Theory of computing

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

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

  2012influential reference
• Tight upper tail bounds for cliques

  2011cited by this paper
• Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems

  2011influential reference
• Upper tails for triangles

  2010cited by this paper
• Approximation algorithms for homogeneous polynomial optimization with quadratic constraints

  2010influential reference
• The missing log in large deviations for triangle counts

  2010cited by this paper
• Random Tensors and Planted Cliques

  2009cited by this paper
• Sums of Squares, Moment Matrices and Optimization Over Polynomials

  2009cited by this paper
• Moments, Positive Polynomials And Their Applications

  2009influential reference
• A new approach to the planted clique problem

  2008influential reference
• Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies

  2008influential reference
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey

  2008cited by this paper
• A PTAS for the minimization of polynomials of fixed degree over the simplex

  2006influential reference
• Divide and conquer martingales and the number of triangles in a random graph

  2004cited by this paper
• Upper tails for subgraph counts in random graphs

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

  2003cited by this paper
• On the advantage over a random assignment

  2002cited by this paper
• Deterministic and randomized polynomial-time approximation of radii

  2001cited by this paper
• A Large Deviation Result on the Number of Small Subgraphs of a Random Graph

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

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

  1999cited by this paper
• Block diagonally dominant matrices and generalizations of the Gerschgorin circle theorem

  1962cited by this paper

• SoS Certifiability of Subgaussian Distributions and Its Algorithmic Applications

  2024cites this paper
• Learning the Closest Product State

  2024cites this paper
• Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold

  2024cites this paper
• A hierarchy of eigencomputations for polynomial optimization on the sphere

  2023cites this paper
• New SDP Roundings and Certifiable Approximation for Cubic Optimization

  2023influential citation
• Semidefinite Relaxations of Products of Nonnegative Forms on the Sphere

  2021cites this paper
• Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems

  2020cites this paper
• THE UNIVERSITY OF CHICAGO SPHERICAL DISCREPANCY A DISSERTATION SUBMITTED TO THE FACULTY OF THE DIVISION OF THE PHYSICAL SCIENCES IN CANDIDACY FOR THE DEGREE OF MASTER OF SCIENCE DEPARTMENT OF COMPUTER SCIENCE BY CHRIS JONES

  2019cites this paper
• The sum-of-squares hierarchy on the sphere and applications in quantum information theory

  2019cites this paper
• Classical and Quantum Algorithms for Tensor Principal Component Analysis

  2019cites this paper
• Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere

  2019cites this paper
• Proposal On the Approximability of Injective Tensor Norms

  2019cites this paper
• A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis

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

  2017cites this paper
• Graph Matrices: Norm Bounds and Applications.

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

  2016cites this paper