Thomas Watson: Query-to-communication lifting for BPP

PRACTICALITIES

Lunch is served at 12:00 noon (register at https://tinyurl.com/TCS171206 at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.

ABSTRACT

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