On the Power of Many One-Bit Provers

Per Austrin, Johan Håstad, Rafael Pass

We study the class of languages, denoted by $\MIP[k, 1-ε, s]$, which have $k$-prover games where each prover just sends a \emph{single} bit, with completeness $1-\epsilon$ and soundness e…