Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SUMS OF SQUARES:
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 >>>




ISSN 1433-8092 | Imprint