Name
Abstract | ||
|---|---|---|
The fooling pairs method is one of the standard methods for proving lower bounds for deterministic two-player communication complexity. We study fooling pairs in the context of randomized communication complexity. We show that every fooling pair induces far away distributions on transcripts of private-coin protocols. We use the above to conclude that the private-coin randomized e-error communication complexity of a function f with a fooling set S is at least order log log vertical bar S vertical bar/epsilon. This relationship was earlier known to hold only for constant values of e. The bound we prove is tight, for example, for the equality and greater-than functions. As an application, we exhibit the following dichotomy: for every boolean function f and integer n, the (1/3)-error public-coin randomized communication complexity of the function V-i(=1)n f(x(i),y(i)) is either at most c or at least n/c, where c > 0 is a universal constant. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-48314-6_4 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Combinatorics,Communication complexity,Mathematics | Journal | 9988 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shay Moran | 1 | 63 | 27.30 |
| Makrand Sinha | 2 | 12 | 3.67 |
| Amir Yehudayoff | 3 | 530 | 43.83 |