Revised: June 8, 2015

Published: August 15, 2016

**Keywords:**communication complexity, set-disjointness, complexity classes

**Categories:**complexity, communication complexity, disjointness, complexity classes, special issue, RANDOM, APPROX-RANDOM 2014 special issue

**ACM Classification:**F.1.3

**AMS Classification:**68Q17, 68Q15

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