Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SUM-OF-SQUARES HIERARCHY:
Reports tagged with sum-of-squares hierarchy:
TR16-079 | 2nd May 2016
Adam Kurpisz, Samuli Lepp\"anen, Monaldo Mastrolilli

#### Sum-of-squares hierarchy lower bounds for symmetric formulations

We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of well-behaved'' univariate polynomial inequalities.

We illustrate the technique on ... more >>>

TR16-185 | 18th November 2016
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

#### Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere

Revisions: 1

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)|$. Besides its fundamental nature, this problem arises in many diverse contexts ranging from tensor and operator norms to graph expansion to quantum information ... more >>>

ISSN 1433-8092 | Imprint