Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JASON LI:
All reports by Author Jason Li:

TR16-142 | 11th September 2016
Jason Li, Ryan O'Donnell

Bounding laconic proof systems by solving CSPs in parallel

Revisions: 1

We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that MIP1$[k,c,s] \subseteq $ PSPACE provided $s/c \leq (.62-o(1))k/2^k$, resolving a question of Austrin, HÃ¥stad, and ... more >>>




ISSN 1433-8092 | Imprint