Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SOS:
Reports tagged with SOS:
TR15-053 | 7th April 2015
Massimo Lauria, Jakob Nordström

Tight Size-Degree Bounds for Sums-of-Squares Proofs

We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size n^{Omega(d)} for values of d = d(n) from constant all the way up to n^{delta} for some universal constant delta. This shows that ... more >>>


TR17-060 | 9th April 2017
Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari

Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

Revisions: 1

We prove that for every function $G\colon\{0,1\}^n \rightarrow \mathbb{R}^m$, if every output of $G$ is a polynomial (over $\mathbb{R}$) of degree at most $d$ of at most $s$ monomials and $m > \widetilde{O}(sn^{\lceil d/2 \rceil})$, then there is a polynomial time algorithm that can distinguish a vector of the form ... more >>>


TR24-010 | 19th January 2024
Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

Black-Box PPP is not Turing-Closed

Revisions: 1

The complexity class PPP contains all total search problems many-one reducible to the PIGEON problem, where we are given a succinct encoding of a function mapping n+1 pigeons to n holes, and must output two pigeons that collide in a hole. PPP is one of the “original five” syntactically-defined subclasses ... more >>>




ISSN 1433-8092 | Imprint