TY - GEN
T1 - Fooling pairs in randomized communication complexity
AU - Moran, Shay
AU - Sinha, Makrand
AU - Yehudayoff, Amir
N1 - A. Yehudayoff—Horev fellow – supported by the Taub foundation. Supported by ISF and BSF.
PY - 2016
Y1 - 2016
N2 - 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 ε-error communication complexity of a function f with a fooling set S is at least order log log |S|/ε. This relationship was earlier known to hold only for constant values of ε. The bound we prove is tight, for example, for the equality and greaterthan 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 Vni=1 f(xi, yi) is either at most c or at least n/c, where c > 0 is a universal constant.
AB - 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 ε-error communication complexity of a function f with a fooling set S is at least order log log |S|/ε. This relationship was earlier known to hold only for constant values of ε. The bound we prove is tight, for example, for the equality and greaterthan 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 Vni=1 f(xi, yi) is either at most c or at least n/c, where c > 0 is a universal constant.
UR - http://www.scopus.com/inward/record.url?scp=84996619253&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84996619253&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-48314-6_4
DO - 10.1007/978-3-319-48314-6_4
M3 - Conference contribution
AN - SCOPUS:84996619253
SN - 9783319483139
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 49
EP - 59
BT - Structural Information and Communication Complexity - 23rd International Colloquium, SIROCCO 2016, Revised Selected Papers
A2 - Suomela, Jukka
PB - Springer
T2 - 23rd International Colloquium on Structural Information and Communication Complexity, SIROCCO 2016
Y2 - 19 July 2016 through 21 July 2016
ER -