arXiv:2511.04794

Pseudodeterministic Communication Complexity

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

Published Nov 6, 2025• 0 citations

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.

DOI: 10.48550/arxiv.2511.04794

Related papers

Pseudodeterministic Communication Complexity

Mika Göös, Nathaniel Harms, Artur Riazanov +3 more

ACM Symposium on Theory of Computing (STOC)Jun 9, 20260 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.26425Aug 26, 20260 citations

Improved Separations between Quantum and Classical Communication Complexity of Total Functions

François Le Gall

quant-pharXiv:2609.16726Sep 16, 20260 citations

One-Way Communication Complexity of Partial XOR Functions

Vladimir V. Podolskii, Sluch, Dmitrii

arXiv:2310.20606Oct 31, 20230 citations

Constant-round quantum advantage in communication complexity for total functions

Atsuya Hasegawa, François Le Gall

We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.

quant-pharXiv:2608.19787Aug 21, 20260 citations

An exponential separation between entanglement-assisted and unassisted one-way quantum communication

Ryan Anselm, Srijita Kundu, Olivier Lalonde +1 more

quant-pharXiv:2610.02099Oct 2, 20260 citations

arXiv:2511.04794

Pseudodeterministic Communication Complexity

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

Published Nov 6, 2025• 0 citations

arXiv HTML PDF

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.

DOI: 10.48550/arxiv.2511.04794

Related papers

Pseudodeterministic Communication Complexity

Mika Göös, Nathaniel Harms, Artur Riazanov +3 more

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.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.

ACM Symposium on Theory of Computing (STOC)Jun 9, 20260 citations

Pseudodeterminism and MA != NP^BPP in Communication Complexity

Thomas W. Watson

arXiv:2608.26425Aug 26, 20260 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.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.16726Sep 16, 20260 citations

One-Way Communication Complexity of Partial XOR Functions

Vladimir V. Podolskii, Sluch, Dmitrii

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.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.20606Oct 31, 20230 citations

Constant-round quantum advantage in communication complexity for total functions

Atsuya Hasegawa, François Le Gall

quant-pharXiv:2608.19787Aug 21, 20260 citations

An exponential separation between entanglement-assisted and unassisted one-way quantum communication

Ryan Anselm, Srijita Kundu, Olivier Lalonde +1 more

A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions $f_n\colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ that can be computed with $O(\log n)$ bits of one-way classical communication given prior entanglement, but that require $Ω(n^{1/3})$ qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions $f_n\colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ that can be computed with $O(\log n)$ bits of one-way classical communication given prior entanglement, but that require $Ω(n^{1/3})$ qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.

quant-pharXiv:2610.02099Oct 2, 20260 citations

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)}

\tildeΩ(\sqrt n)

randomized communication with two quantum messages, and versus

Ω(n^{1-\varepsilon})

for every fixed

0<\varepsilon<1

with more quantum messages.

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

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)

F

is exactly equal to nonadaptive parity decision tree complexity

NADT^{\oplus}(f)

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.

f_n\colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}

that can be computed with

O(\log n)

bits of one-way classical communication given prior entanglement, but that require

Ω(n^{1/3})

qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.