2026-08-15T19:36:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4734 2024-03-06T10:35:20Z ddc:004 open_access

Communication Complexity of Set-Disjointness for All Probabilities Göös, Mika Watson, Thomas Communication Complexity Set-Disjointness All Probabilities 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mika Göös and Thomas Watson 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.721 urn:nbn:de:0030-drops-47342 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.721 eng https://creativecommons.org/licenses/by/3.0/legalcode