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.

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

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.