Query-to-Communication Lifting for BPP

2017/03/22 by Göös, Mika, Pitassi, Toniann, Watson, Thomas · 4 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1703.07666

Abstract

For any n-bit boolean function f, we show that the randomized communication complexity of the composed function f∘ gⁿ, 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.

Cited by

• A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
• Pseudodeterministic Communication Complexity
• Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
• Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication

Related

• Separations in Query Complexity Based on Pointer Functions
• Pseudodeterministic Communication Complexity
• An Optimal Separation of Randomized and Quantum Query Complexity
• Low-Sensitivity Functions from Unambiguous Certificates
• Quantum and Classical Communication Complexity of Permutation-Invariant Functions