Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SUM-OF-SQUARES:
Reports tagged with sum-of-squares:
TR13-105 | 29th July 2013
Raghu Meka, Avi Wigderson

#### Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique

Revisions: 1

Finding cliques in random graphs and the closely related planted'' clique variant, where a clique of size t is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for t = ... more >>>

TR17-154 | 12th October 2017
Christoph Berkholz

#### The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs

We relate different approaches for proving the unsatisfiability of a system of real polynomial equations over Boolean variables. On the one hand, there are the static proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, we consider polynomial calculus, ... 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 >>>

TR19-142 | 23rd October 2019
Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch, Iddo Tzameret

#### Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?

We introduce the binary value principle' which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of this instance, ... more >>>

TR21-070 | 13th May 2021
Shuo Pang

#### SOS lower bound for exact planted clique

We prove a SOS degree lower bound for the planted clique problem on Erd{\"o}s-R\'enyi random graphs $G(n,1/2)$. The bound we get is degree $d=\Omega(\epsilon^2\log n/\log\log n)$ for clique size $\omega=n^{1/2-\epsilon}$, which is almost tight. This improves the result of \cite{barak2019nearly} on the `soft'' version of the problem, where the family ... more >>>

ISSN 1433-8092 | Imprint