Revised: June 8, 2015
Published: August 15, 2016
Abstract: [Plain Text Version]
We study $\sdisj$ in a generalized model of randomized two-party communication where the probability of acceptance must be at least $\alpha(n)$ on yes-inputs and at most $\beta(n)$ on no-inputs, for some functions $\alpha(n)> \beta(n)$. Our main result is a complete characterization of the private-coin communication complexity of $\sdisj$ for all functions $\alpha$ and $\beta$, and a near-complete characterization for public-coin protocols. In particular, we obtain a simple proof of a theorem of Braverman and Moitra (STOC 2013), who studied the case where $\alpha=1/2+\epsilon(n)$ and $\beta=1/2-\epsilon(n)$. The following contributions play a crucial role in our characterization and are interesting in their own right.
- We introduce two communication analogues of the classical complexity class that captures small bounded-error computations: we define a “restricted” class $\mathsf{SBP}$ (which lies between $\mathsf{MA}$ and $\mathsf{AM}$) and an “unrestricted” class $\mathsf{USBP}$. The distinction between them is analogous to the distinction between the well-known communication classes $\mathsf{PP}$ and $\mathsf{UPP}$.
- We show that the $\mathsf{SBP}$ communication complexity is precisely captured by the classical corruption lower bound method. This sharpens a theorem of Klauck (CCC 2003).
- We use information complexity arguments to prove a linear lower bound on the $\mathsf{USBP}$ complexity of $\sdisj$.
A preliminary version of this paper appeared in the Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM), 2014.