Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-148 | 5th April 2020 22:04

Communication Complexity with Small Advantage

RSS-Feed




Revision #1
Authors: Thomas Watson
Accepted on: 5th April 2020 22:04
Downloads: 272
Keywords: 


Abstract:

We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least $\epsilon$ greater than one over the codomain size of the function. Previously, Braverman and Moitra (STOC 2013) showed that the set-intersection function requires $\Theta(\epsilon n)$ communication to achieve advantage $\epsilon$. Building on this, we prove the same bound for several variants of set-intersection: (1) the classic "tribes" function obtained by composing with And (provided $1/\epsilon$ is at most the width of the And), and (2) the variant where the sets are uniquely intersecting and the goal is to determine partial information about (say, certain bits of the index of) the intersecting coordinate.


Paper:

TR16-148 | 23rd September 2016 03:54

Communication Complexity with Small Advantage





TR16-148
Authors: Thomas Watson
Publication: 23rd September 2016 09:15
Downloads: 1078
Keywords: 


Abstract:

We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least $\epsilon$ greater than one over the codomain size of the function. Previously, Braverman and Moitra (STOC 2013) showed that the set-intersection function requires $\Theta(\epsilon n)$ communication to achieve advantage $\epsilon$. Building on this, we prove the same bound for several variants of set-intersection: (1) the classic "tribes" function obtained by composing with And (provided $1/\epsilon$ is at most the width of the And), and (2) the variant where the sets are uniquely intersecting and the goal is to determine partial information about (say, certain bits of the index of) the intersecting coordinate.



ISSN 1433-8092 | Imprint