Volume 12 (2016) Article 9 pp. 1-23
APPROX-RANDOM 2014 Special Issue
Communication Complexity of Set-Disjointness for All Probabilities
by
Revised: June 8, 2015
Published: August 15, 2016
[PDF (318K)]    [PS (1621K)]    [PS.GZ (369K)]
[Source ZIP]
Keywords: communication complexity, set-disjointness, complexity classes
ACM Classification: F.1.3
AMS Classification: 68Q17, 68Q15

Abstract: [Plain Text Version]

$\newcommand{\sdisj}{\textsf{Set-Disjointness}}$

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.

1. 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}$.
2. 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).
3. 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.