On the Power of Many One-Bit Provers

We study the class of languages, denoted by $\text{MIP}[k,1-ϵ,s]$, which have $k$-prover games where each prover just sends a \emph{single} bit, with completeness $1-ϵ$ and soundness error $s$. For the case that $k=1$ (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson ({\em Computational Complexity’02}) demonstrate that $\text{SZK}$ exactly characterizes languages having 1-bit proof systems with"non-trivial" soundness (i.e., $1\mathrm{/}2<s\le 1-2ϵ$). We demonstrate that for the case that $k\ge 2$, 1-bit $k$-prover games exhibit a significantly richer structure:

• (Folklore) When $s\le \frac{1}{2^k}-ϵ$, $\MIP[k, 1-\epsilon, s] = \BPP$;
• When $\frac{1}{2^k}+ϵ\le s<\frac{2}{2^k}-ϵ$, $\MIP[k, 1-\epsilon, s] = \SZK$;
• When $s\ge \frac{2}{2^k}+ϵ$, $\AM \subseteq \MIP[k, 1-\epsilon, s]$;
• For $s\le 0.62k\mathrm{/}{2}^k$ and sufficiently large $k$, $\MIP[k, 1-\epsilon, s] \subseteq \EXP$;
• For $s\ge 2k\mathrm{/}{2}^k$, $\text{MIP}[k,1,1-ϵ,s]=\text{NEXP}$. As such, 1-bit $k$-prover games yield a natural “quantitative” approach to relating complexity classes such as $\text{BPP}$,$\text{SZK}$,$\text{AM}$, $\text{EXP}$, and $\text{NEXP}$. We leave open the question of whether a more fine-grained hierarchy (between $\text{AM}$ and $\text{NEXP}$) can be established for the case when $s \geq \frac{2}{2^k} + \epsilon$.