Fooling pairs in randomized communication complexity

Shay Moran, Makrand Sinha, Amir Yehudayoff

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ε-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.

Original languageEnglish (US)
Title of host publicationStructural Information and Communication Complexity - 23rd International Colloquium, SIROCCO 2016, Revised Selected Papers
EditorsJukka Suomela
PublisherSpringer
Pages49-59
Number of pages11
ISBN (Print)9783319483139
DOIs
StatePublished - 2016
Externally publishedYes
Event23rd International Colloquium on Structural Information and Communication Complexity, SIROCCO 2016 - Helsinki, Finland
Duration: Jul 19 2016Jul 21 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9988 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd International Colloquium on Structural Information and Communication Complexity, SIROCCO 2016
Country/TerritoryFinland
CityHelsinki
Period7/19/167/21/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Fooling pairs in randomized communication complexity'. Together they form a unique fingerprint.

Cite this