Abstract

We exhibit an -bit partial function with randomized communication complexity but such that any completion of this function into a total one requires randomized communication complexity . In particular, this shows an exponential separation between randomized and pseudodeterministic communication protocols. Previously, Gavinsky (2025) showed an analogous separation in the weaker model of parity decision trees. We use lifting techniques to extend his proof idea to communication complexity.

Joint work with Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov.

Time

Thursday, Jan. 8, 14:00--15:00

Speaker

Weiqiang Yuan

Room

Room 602