BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Query-to-Communication Lifting Göös, Mika


This will be a tutorial-style talk, with a particular focus on the following result. 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 a small 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. Joint work with Toniann Pitassi and Thomas Watson.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International