Göös, Mika ;
Watson, Thomas
Communication Complexity of SetDisjointness for All Probabilities
Abstract
We study setdisjointness in a generalized model of randomized twoparty communication where the probability of acceptance must be at least alpha(n) on yesinputs and at most beta(n) on noinputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the privatecoin communication complexity of setdisjointness for all functions alpha and beta, and a nearcomplete characterization for publiccoin 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/2epsilon(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 boundederror 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 wellknown 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 setdisjointness.
BibTeX  Entry
@InProceedings{gs_et_al:LIPIcs:2014:4734,
author = {Mika G{\"o}{\"o}s and Thomas Watson},
title = {{Communication Complexity of SetDisjointness for All Probabilities}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
pages = {721736},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897743},
ISSN = {18688969},
year = {2014},
volume = {28},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4734},
URN = {urn:nbn:de:0030drops47342},
doi = {10.4230/LIPIcs.APPROXRANDOM.2014.721},
annote = {Keywords: Communication Complexity, SetDisjointness, All Probabilities}
}
2014
Keywords: 

Communication Complexity, SetDisjointness, All Probabilities 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Issue date: 

2014 
Date of publication: 

2014 