Theory of Computing
-------------------
Title     : Communication Complexity of Set-Disjointness for All Probabilities
Authors   : Mika Goos and Thomas Watson
Volume    : 12
Number    : 9
Pages     : 1-23
URL       : https://theoryofcomputing.org/articles/v012a009

Abstract
--------

We study set-disjointness 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 set-disjointness 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 SBP (which lies
  between MA and AM) and an "unrestricted" class USBP. The
  distinction between them is analogous to the distinction between
  the well-known communication classes PP and UPP.

  2. We show that the 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 USBP complexity of set-disjointness.


A preliminary version of this paper appeared in the Proceedings of
the 18th International Workshop on Randomization and Computation
(RANDOM), 2014.