Query-to-Communication Lifting for BPP

Mika Göös, Toniann Pitassi, Thomas Watson

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…