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• 0 citations

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

Pseudodeterministic Communication Complexity

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

arXiv:2511.04794Nov 6, 20250 citations

Improved Separations between Quantum and Classical Communication Complexity of Total Functions

François Le Gall

quant-pharXiv:2609.16726Sep 16, 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

One-Way Communication Complexity of Partial XOR Functions

Vladimir V. Podolskii, Dmitrii Sluch

Leibniz international proceedings in informaticsJan 1, 20240 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

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• 0 citations

Publisher

Abstract

DOI: 10.1145/3798129.3800907

Related papers

Pseudodeterministic Communication Complexity

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

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

arXiv:2511.04794Nov 6, 20250 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

Pseudodeterminism and MA != NP^BPP in Communication Complexity

Thomas W. Watson

arXiv:2608.26425Aug 26, 20260 citations

One-Way Communication Complexity of Partial XOR Functions

Vladimir V. Podolskii, Dmitrii Sluch

Boolean function F(x,y) for x,y ∈ {0,1}ⁿ is an XOR function if F(x,y) = f(x⊕ y) for some function f on n input bits, where ⊕ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing the 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-way communication complexity D_{cc}^{→}(F) of F is exactly equal to non-adaptive parity decision tree complexity NADT^{⊕}(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 study of a similar connection for partial functions. We show that in the case of one-way communication complexity whether these measures are equal, depends on the number of undefined inputs of f. More precisely, if D_{cc}^{→}(F) = t and f is undefined on at most O((2^{n-t})/(√{n-t})) inputs, then NADT^{⊕}(f) = t. We also provide stronger bounds in extreme cases of small and large complexity. We show that the restriction on the number of undefined inputs in these results is unavoidable. That is, for a wide range of values of D_{cc}^{→}(F) and NADT^{⊕}(f) (from constant to n-2) we provide partial functions (with more than Ω((2^{n-t})/(√{n-t})) undefined inputs, where t = D_{cc}^{→}) for which D_{cc}^{→}(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-way 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 the Boolean Fourier analysis and thus, 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 ∈ {0,1}ⁿ is an XOR function if F(x,y) = f(x⊕ y) for some function f on n input bits, where ⊕ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing the 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-way communication complexity D_{cc}^{→}(F) of F is exactly equal to non-adaptive parity decision tree complexity NADT^{⊕}(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 study of a similar connection for partial functions. We show that in the case of one-way communication complexity whether these measures are equal, depends on the number of undefined inputs of f. More precisely, if D_{cc}^{→}(F) = t and f is undefined on at most O((2^{n-t})/(√{n-t})) inputs, then NADT^{⊕}(f) = t. We also provide stronger bounds in extreme cases of small and large complexity. We show that the restriction on the number of undefined inputs in these results is unavoidable. That is, for a wide range of values of D_{cc}^{→}(F) and NADT^{⊕}(f) (from constant to n-2) we provide partial functions (with more than Ω((2^{n-t})/(√{n-t})) undefined inputs, where t = D_{cc}^{→}) for which D_{cc}^{→}(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-way 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 the Boolean Fourier analysis and thus, 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.

Leibniz international proceedings in informaticsJan 1, 20240 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)}

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

\tildeΩ(\sqrt n)

randomized communication with two quantum messages, and versus

Ω(n^{1-\varepsilon})

for every fixed

0<\varepsilon<1

with more quantum messages.

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.