Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Sums of squares:
TR14-059 | 21st April 2014
Boaz Barak, David Steurer

Sum-of-squares proofs and the quest toward optimal algorithms

Revisions: 2

In order to obtain the best-known guarantees, algorithms are traditionally tailored to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method, surprisingly suggest that this tailoring is not necessary and that a single efficient algorithm could achieve best possible ... more >>>

TR22-105 | 18th July 2022
Ilario Bonacina, Nicola Galesi, Massimo Lauria

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size.

more >>>

ISSN 1433-8092 | Imprint