Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Fooling Pairs in Randomized Communication Complexity
verfasst von : Shay Moran, Makrand Sinha, Amir Yehudayoff
Erschienen in: Structural Information and Communication Complexity
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 \(\varepsilon \)-error communication complexity of a function f with a fooling set \(\mathcal S\) is at least order \(\log \frac{\log |\mathcal S|}{\varepsilon }\). This relationship was earlier known to hold only for constant values of \(\varepsilon \). 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 \(\bigvee _{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.