Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-053 | 22nd March 2017 16:30

Query-to-Communication Lifting for BPP

RSS-Feed




TR17-053
Authors: Mika Göös, Toniann Pitassi, Thomas Watson
Publication: 22nd March 2017 18:52
Downloads: 322
Keywords: 


Abstract:

For any $n$-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f\circ g^n$, where $g$ is an index gadget, is characterized by the randomized decision tree complexity of $f$. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs.\ quantum) automatically imply analogous separations in communication complexity.



ISSN 1433-8092 | Imprint