Volume 12 (2016) Article 9 pp. 1-23
APPROX-RANDOM 2014 Special Issue

Communication Complexity of Set-Disjointness for All Probabilities

by Mika Göös and Thomas Watson

Received: December 21, 2014
Revised: June 8, 2015
Published: August 15, 2016

$\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.

DOI: 10.4086/toc.2016.v012a009

© 2016 Mika Göös and Thomas Watson
Licensed under a Creative Commons Attribution License (CC-BY)