Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SUM OF SQUARES:
Reports tagged with Sum of Squares:
TR13-184 | 23rd December 2013
Boaz Barak, Jonathan Kelner, David Steurer

#### Rounding Sum-of-Squares Relaxations

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly ... more >>>

TR14-142 | 1st November 2014
Subhash Khot, Dana Moshkovitz

#### Candidate Lasserre Integrality Gap For Unique Games

We propose a candidate Lasserre integrality gap construction for the Unique Games problem.
Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution ... more >>>

TR16-058 | 12th April 2016
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin

#### A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

We prove that with high probability over the choice of a random graph $G$ from the Erd\H{o}s-R\'enyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$.
This yields a nearly tight ... more >>>

TR16-141 | 11th September 2016
Ryan O'Donnell

Revisions: 1

Suppose we want to minimize a polynomial $p(x) = p(x_1, \dots, x_n)$, subject to some polynomial constraints $q_1(x), \dots, q_m(x) \geq 0$, using the Sum-of-Squares (SOS) SDP hierarachy. Assume we are in the "explicitly bounded" ("Archimedean") case where the constraints include $x_i^2 \leq 1$ for all $1 \leq i \leq ... more >>> TR17-011 | 22nd January 2017 Boaz Barak, Pravesh Kothari, David Steurer #### Quantum entanglement, sum of squares, and the log rank conjecture For every constant$\epsilon>0$, we give an$\exp(\tilde{O}(\sqrt{n}))$-time algorithm for the$1$vs$1-\epsilon$Best Separable State (BSS) problem of distinguishing, given an$n^2\times n^2$matrix$M$corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state$\rho$that$M$accepts with probability$1$, ... more >>> TR19-106 | 12th August 2019 Noah Fleming, Pravesh Kothari, Toniann Pitassi #### Semialgebraic Proofs and Efficient Algorithm Design Revisions: 4 Over the last twenty years, an exciting interplay has emerged between proof systems and algorithms. Some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself. This connection has perhaps been the most consequential ... more >>> TR20-012 | 14th February 2020 Dmitry Sokolov #### (Semi)Algebraic Proofs over$\{\pm 1\}$Variables One of the major open problems in proof complexity is to prove lower bounds on$AC_0[p]$-Frege proof systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove lower bounds on the size for Polynomial Calculus over the$\{\pm 1\}\$ basis. In this ... more >>>

TR20-136 | 11th September 2020
Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

#### Explicit and structured sum of squares lower bounds from high dimensional expanders

We construct an explicit family of 3XOR instances which is hard for Omega(sqrt(log n)) levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time.
Our construction is based on the high-dimensional expanders devised by Lubotzky, ... more >>>

ISSN 1433-8092 | Imprint