Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2511.04794 · ACM Symposium on Theory of Computing (STOC)

Pseudodeterministic Communication Complexity

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

Published Jun 9, 2026• 3 citations
arXivHTMLPDF

Abstract

We exhibit an n-bit partial function with randomized communication complexity O(logn) 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 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.

DOI
10.1145/3798129.3800907

Related papers

One-Way Communication Complexity of Partial XOR Functions

Vladimir V. Podolskii, Dmitrii Sluch

Boolean function $F(x,y)$ for $x,y \in \{0,1\}^n$ is an XOR function if $F(x,y)=f(x\oplus y)$ for some function $f$ on $n$ input bits, where $\oplus$ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing Fourier analytic technique. For total XOR functions it is known that deterministic communication complexity of $F$ is closely related to parity decision tree complexity of $f$. Montanaro and Osbourne (2009) observed that one-sided communication complexity $D_{cc}^{\rightarrow}(F)$ of $F$ is exactly equal to nonadaptive parity decision tree complexity $NADT^{\oplus}(f)$ of $f$. Hatami et al. (2018) showed that unrestricted communication complexity of $F$ is polynomially related to parity decision tree complexity of $f$. We initiate the studies of a similar connection for partial functions. We show that in case of one-sided communication complexity whether these measures are equal, depends on the number of undefined inputs of $f$. On the one hand, if $D_{cc}^{\rightarrow}(F)=t$ and $f$ is undefined on at most $O(\frac{2^{n-t}}{\sqrt{n-t}})$, then $NADT^{\oplus}(f)=t$. On the other hand, for a wide range of values of $D_{cc}^{\rightarrow}(F)$ and $NADT^{\oplus}(f)$ (from constant to $n-2$) we provide partial functions for which $D_{cc}^{\rightarrow}(F) < NADT^{\oplus}(f)$. In particular, we provide a function with an exponential gap between the two measures. Our separation results translate to the case of two-sided communication complexity as well, in particular showing that the result of Hatami et al. (2018) cannot be generalized to partial functions. Previous results for total functions heavily rely on Boolean Fourier analysis and the technique does not translate to partial functions. For the proofs of our results we build a linear algebraic framework instead. Separation results are proved through the reduction to covering codes.

arXiv:2310.20606•Leibniz international proceedings in informatics•Oct 31, 2023•1 citation

Quantum versus Randomized Communication Complexity, with Efficient Players

Uma Girish, Ran Raz, Avishay Tal

We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient , in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N , such that: f can be computed by a simultaneous-message quantum protocol with communication complexity polylog( N ) (where at the beginning of the protocol Alice and Bob also have polylog( N ) entangled EPR pairs). Any classical randomized protocol for f , with any number of rounds, has communication complexity at least \(\tilde{\Omega}\left(N^{1/4}\right)\) . All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog( N ) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of \(\Omega\left(N^{1/2}\right)\) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.

arXiv:1911.02218•Computational Complexity•Oct 28, 2022•14 citations

Improved Separations between Quantum and Classical Communication Complexity of Total Functions

François Le Gall

We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus $\tildeΩ(\sqrt n)$ randomized communication with two quantum messages, and versus $Ω(n^{1-\varepsilon})$ for every fixed $0<\varepsilon<1$ with more quantum messages.

quant-pharXiv:2609.16726•Sep 16, 2026•2 citations

Pseudodeterminism and MA != NP^BPP in Communication Complexity

Thomas W. Watson

We prove an exponential separation between zero-sided-error randomized and two-sided-error pseudodeterministic communication complexities of partial boolean functions. This qualitatively improves and simplifies the proof of the separation by Göös, Harms, Riazanov, Sofronova, Sokolov, and Yuan (STOC 2026), which had a two-sided-error randomized upper bound. Then, we generalize our technique to separate the communication complexity analogues of MA and NP^BPP.

arXiv:2608.26425•Aug 26, 2026•0 citations

Query-to-Communication Lifting for BPP

Mika Göös, Toniann Pitassi, Thomas W. 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 the randomized decision tree complexity of $f$. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs. quantum) automatically imply analogous separations in communication complexity.

arXiv:1703.07666•SIAM Journal on Computing•Oct 1, 2017•87 citations

Equality Alone Does not Simulate Randomness

Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is "Equality". In this work we show that even allowing access to an "Equality" oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function on n bits with randomized one-sided communication complexity O(log n), but such that every deterministic protocol with access to "Equality" oracle needs Omega(n) cost to compute it. Additionally we exhibit a natural and strict infinite hierarchy within BPP, starting with the class P^{EQ} at its bottom.

Leibniz international proceedings in informatics•Jan 1, 2019•18 citations
We exhibit an n-bit partial function with randomized communication complexity O(logn) 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 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.
Boolean function F(x,y)F(x,y)F(x,y) for x,y∈{0,1}nx,y \in \{0,1\}^nx,y∈{0,1}n is an XOR function if F(x,y)=f(x⊕y)F(x,y)=f(x\oplus y)F(x,y)=f(x⊕y) for some function fff on nnn input bits, where ⊕\oplus⊕ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing Fourier analytic technique. For total XOR functions it is known that deterministic communication complexity of FFF is closely related to parity decision tree complexity of fff. Montanaro and Osbourne (2009) observed that one-sided communication complexity Dcc→(F)D_{cc}^{\rightarrow}(F)Dcc→​(F) of FFF is exactly equal to nonadaptive parity decision tree complexity NADT⊕(f)NADT^{\oplus}(f)NADT⊕(f) of fff. Hatami et al. (2018) showed that unrestricted communication complexity of FFF is polynomially related to parity decision tree complexity of fff. We initiate the studies of a similar connection for partial functions. We show that in case of one-sided communication complexity whether these measures are equal, depends on the number of undefined inputs of fff. On the one hand, if Dcc→(F)=tD_{cc}^{\rightarrow}(F)=tDcc→​(F)=t and fff is undefined on at most O(2n−tn−t)O(\frac{2^{n-t}}{\sqrt{n-t}})O(n−t​2n−t​), then NADT⊕(f)=tNADT^{\oplus}(f)=tNADT⊕(f)=t. On the other hand, for a wide range of values of Dcc→(F)D_{cc}^{\rightarrow}(F)Dcc→​(F) and NADT⊕(f)NADT^{\oplus}(f)NADT⊕(f) (from constant to n−2n-2n−2) we provide partial functions for which Dcc→(F)<NADT⊕(f)D_{cc}^{\rightarrow}(F) < NADT^{\oplus}(f)Dcc→​(F)<NADT⊕(f). In particular, we provide a function with an exponential gap between the two measures. Our separation results translate to the case of two-sided communication complexity as well, in particular showing that the result of Hatami et al. (2018) cannot be generalized to partial functions. Previous results for total functions heavily rely on Boolean Fourier analysis and the technique does not translate to partial functions. For the proofs of our results we build a linear algebraic framework instead. Separation results are proved through the reduction to covering codes.
We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient , in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N , such that: f can be computed by a simultaneous-message quantum protocol with communication complexity polylog( N ) (where at the beginning of the protocol Alice and Bob also have polylog( N ) entangled EPR pairs). Any classical randomized protocol for f , with any number of rounds, has communication complexity at least Ω~(N1/4)\tilde{\Omega}\left(N^{1/4}\right)Ω~(N1/4) . All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog( N ) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of Ω(N1/2)\Omega\left(N^{1/2}\right)Ω(N1/2) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.
We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus Ω~(n)\tildeΩ(\sqrt n)Ω~(n​) randomized communication with two quantum messages, and versus Ω(n1−ε)Ω(n^{1-\varepsilon})Ω(n1−ε) for every fixed 0<ε<10<\varepsilon<10<ε<1 with more quantum messages.
For any nnn-bit boolean function fff, we show that the randomized communication complexity of the composed function f∘gnf\circ g^nf∘gn, where ggg is an index gadget, is characterized by the randomized decision tree complexity of fff. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs. quantum) automatically imply analogous separations in communication complexity.
The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is "Equality". In this work we show that even allowing access to an "Equality" oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function on n bits with randomized one-sided communication complexity O(log n), but such that every deterministic protocol with access to "Equality" oracle needs Omega(n) cost to compute it. Additionally we exhibit a natural and strict infinite hierarchy within BPP, starting with the class P^{EQ} at its bottom.