License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.721
URN: urn:nbn:de:0030-drops-47342
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4734/
Go to the corresponding LIPIcs Volume Portal

Göös, Mika ; Watson, Thomas

Communication Complexity of Set-Disjointness for All Probabilities

pdf-format:
51.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{gs_et_al:LIPIcs:2014:4734,
  author =	{Mika G{\"o}{\"o}s and Thomas Watson},
  title =	{{Communication Complexity of Set-Disjointness for All Probabilities}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{721--736},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4734},
  URN =		{urn:nbn:de:0030-drops-47342},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.721},
  annote =	{Keywords: Communication Complexity, Set-Disjointness, All Probabilities}
}

Keywords: Communication Complexity, Set-Disjointness, All Probabilities
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI