Pseudodeterministic Communication Complexity
By: Mika Göös , Nathaniel Harms , Artur Riazanov and more
Potential Business Impact:
Makes computers solve problems much faster.
We exhibit an $n$-bit partial function with randomized communication complexity $O(\log n)$ but such that any completion of this function into a total one requires randomized communication complexity $n^{\Omega(1)}$. In particular, this shows an exponential separation between randomized and \emph{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.
Similar Papers
A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
Computational Complexity
Makes computers use less quantum messages with classical help.
A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
Computational Complexity
Makes computers use less quantum information.
Equality is Far Weaker than Constant-Cost Communication
Computational Complexity
Makes computers solve problems faster without guessing.