Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-142 | 11th September 2016 22:51

Bounding laconic proof systems by solving CSPs in parallel

RSS-Feed




Revision #1
Authors: Jason Li, Ryan O'Donnell
Accepted on: 11th September 2016 22:51
Downloads: 405
Keywords: 


Abstract:

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 Pass. Here MIP1$[k,c,s]$ is the class of languages decidable with completeness $c$ and soundness $s$ by an interactive proof system with $k$ provers, each constrained to communicate just $1$ bit.



Changes to previous version:

Removed ridiculous spurious opening line in which I was testing an alternative to the LaTeX xspace package!


Paper:

TR16-142 | 11th September 2016 22:00

Bounding laconic proof systems by solving CSPs in parallel





TR16-142
Authors: Jason Li, Ryan O'Donnell
Publication: 11th September 2016 22:01
Downloads: 527
Keywords: 


Abstract:

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 Pass. Here MIP1$[k,c,s]$ is the class of languages decidable with completeness $c$ and soundness $s$ by an interactive proof system with $k$ provers, each constrained to communicate just $1$ bit.



ISSN 1433-8092 | Imprint