preprint · arXiv (Cornell University) · 2025

Pseudodeterministic Communication Complexity

Göös, Mika, Harms, Nathaniel, Riazanov, Artur, Sofronova, Anastasia, Sokolov, Dmitry, Yuan, Weiqiang

Cited by 0Open access

Abstract

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^{Ω(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.

Cite this paper

APA 7

Göös, M., Harms, N., Riazanov, A., Sofronova, A., Sokolov, D., & Yuan, W. (2025). Pseudodeterministic Communication Complexity. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2511.04794

MLA 9

Göös, Mika, et al. “Pseudodeterministic Communication Complexity.” arXiv (Cornell University), 2025, https://doi.org/10.48550/arxiv.2511.04794.

Chicago

Göös, Mika, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan. 2025. “Pseudodeterministic Communication Complexity.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2511.04794.

Harvard

Göös, M. et al. (2025) ‘Pseudodeterministic Communication Complexity’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.2511.04794.

BibTeX

@misc{goos2025pseudodeterministic,
  title = {{Pseudodeterministic Communication Complexity}},
  author = {Göös, Mika and Harms, Nathaniel and Riazanov, Artur and Sofronova, Anastasia and Sokolov, Dmitry and Yuan, Weiqiang},
  journal = {arXiv (Cornell University)},
  year = {2025},
  doi = {10.48550/arxiv.2511.04794}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.