Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR17-053 | 22nd March 2017 16:30

#### Query-to-Communication Lifting for BPP

TR17-053
Authors: Mika Göös, Toniann Pitassi, Thomas Watson
Publication: 22nd March 2017 18:52
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