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 is a fifth-year Ph.D. student at EPFL, coadvised by Mika Göös and Ola Svensson. He has broad interests in complexity theory, with a focus on communication complexity, pseudorandomness, and cryptography
Room
Room 602
