Thomas Watson: Query-to-communication lifting for BPP
Time: Wed 2017-12-06 12.00
Location: Room 4523, Lindstedtsvägen 5, KTH CSC 
Participating: Thomas Watson, University of Memphis
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.