Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Bounding laconic proof systems by solving CSPs in parallel

Revision #1
Authors: Jason Li, Ryan O'Donnell
Accepted on: 11th September 2016 22:51
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
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.