__
Revision #1 to TR16-142 | 11th September 2016 22:51
__
#### Bounding laconic proof systems by solving CSPs in parallel

**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!

__
TR16-142 | 11th September 2016 22:00
__

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

**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.