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:1205.0903

A note on a problem in communication complexity

Henning Wunderlich

Published May 4, 2012• 2 citations
arXivHTMLPDF

Abstract

We study bounded-error randomization and majority operators in structural communication complexity. We give a communication-complexity formulation of Tarui's theorem and identify the bounded-error closure of weakly unbounded-error communication with a distributional perturbation of logarithmic margin complexity. Retaining the Boolean guarantee in Tarui's probabilistic polynomials yields the stronger inclusion $\mathsf{PH}^{\mathrm{cc}} \subseteq \mathsf{ZP}\mathbin{\cdot} \mathsf{PP}^{\mathrm{cc}} \subseteq \mathsf{BP}\mathbin{\cdot} \mathsf{PP}^{\mathrm{cc}}$. We also define a majority operator satisfying $\mathsf{PP}\mathbin{\cdot} \mathsf{P}^{\mathrm{cc}} = \mathsf{PP}^{\mathrm{cc}}$ and use Sasaki's majority formula to prove that $\mathord{\oplus}\mathsf{P}^{\mathrm{cc}} \subseteq \mathsf{PP}\mathbin{\cdot} \mathsf{PP}^{\mathrm{cc}}$. For the inner-product function modulo two, both the outer index and each inner protocol have logarithmic cost. Together with Forster's lower bound, this gives an explicit witness to the non-idempotence of the majority operator and to $\mathsf{PP}\mathbin{\cdot} \mathsf{PP}^{\mathrm{cc}} \not\subseteq \mathsf{UPP}^{\mathrm{cc}}$. Both the bounded-error closure and the two-level majority class are contained in $\mathsf{PSPACE}^{\mathrm{cc}}$.

DOI
10.48550/arxiv.1205.0903

Related papers

A linear lower bound on the unbounded error probabilistic communication complexity

Jüurgen Forster

We prove a general lower bound on the complexity of unbounded error probabilistic communication protocols. This result improves on a lower bound for bounded error protocols from Krause (1996). As a simple consequence we get the, to our knowledge, first linear lower bound on the complexity of unbounded error probabilistic communication protocols for the functions defined by Hadamard matrices. We also give an upper bound on the margin of any embedding of a concept class in half spaces.

IEEE Conference on Computational Complexity (CCC)•Nov 13, 2002•15 citations

Quantum-Classical Equivalence for AND-Functions

Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay +2 more

A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form $$ F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), $$ when the outer function $f$ is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function $f$, the bounded-error quantum and classical deterministic communication complexities of the function $f \circ \mathrm{AND}_2$ are polynomially related, up to polylogarithmic factors in $n$. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of $f$. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.

cs.CCCross-listedarXiv:2606.03249•Leibniz international proceedings in informatics•Jun 3, 2026•0 citations

Dual polynomials and communication complexity of $\textsf{XOR}$ functions

Arkadev Chattopadhyay, Nikhil S. Mande

We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f \circ \textsf{XOR}$, called an $\textsf{XOR}$ function. Using this duality, we develop polynomial based techniques for understanding the bounded error ($\textsf{BPP}$) and the weakly-unbounded error ($\textsf{PP}$) communication complexities of $\textsf{XOR}$ functions. We show the following. A weak form of an interesting conjecture of Zhang and Shi (Quantum Information and Computation, 2009) (The full conjecture has just been reported to be independently settled by Hatami and Qian (Arxiv, 2017). However, their techniques are quite different and are not known to yield many of the results we obtain here). Zhang and Shi assert that for symmetric functions $f : \{0, 1\}^n \rightarrow \{-1, 1\}$, the weakly unbounded-error complexity of $f \circ \textsf{XOR}$ is essentially characterized by the number of points $i$ in the set $\{0,1, \dots,n-2\}$ for which $D_f(i) \neq D_f(i+2)$, where $D_f$ is the predicate corresponding to $f$. The number of such points is called the odd-even degree of $f$. We show that the $\textsf{PP}$ complexity of $f \circ \textsf{XOR}$ is $Ω(k/ \log(n/k))$. We resolve a conjecture of a different Zhang characterizing the Threshold of Parity circuit size of symmetric functions in terms of their odd-even degree. We obtain a new proof of the exponential separation between $\textsf{PP}^{cc}$ and $\textsf{UPP}^{cc}$ via an $\textsf{XOR}$ function. We provide a characterization of the approximate spectral norm of symmetric functions, affirming a conjecture of Ada et al. (APPROX-RANDOM, 2012) which has several consequences. Additionally, we prove strong $\textsf{UPP}$ lower bounds for $f \circ \textsf{XOR}$, when $f$ is symmetric and periodic with period $O(n^{1/2-ε})$, for any constant $ε> 0$.

arXiv:1704.02537•Apr 8, 2017•2 citations

The communication complexity of distributed estimation

Parikshit Gopalan, Raghu Meka, Prasad Raghavendra +2 more

We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions $p$ and $q$ over domains $X$ and $Y$, respectively. Their goal is to estimate \[ \mathbb{E}_{x \sim p,\, y \sim q}[f(x, y)] \] to within additive error $\varepsilon$ for a bounded function $f$, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of $f$ and the error parameter $\varepsilon$. The random sampling approach -- estimating the mean by averaging $f$ over $O(1/\varepsilon^2)$ random samples -- requires $O(R(f)/\varepsilon^2)$ total communication, where $R(f)$ is the randomized communication complexity of $f$. We design a new debiasing protocol which improves the dependence on $1/\varepsilon$ to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.

arXiv:2511.21015•Nov 26, 2025•0 citations

New lower bounds for CDS and $f$-routing

Atsuya Hasegawa, Ranitha Mataraarachchi

Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case is $f$-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC. Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and $f$-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function. Second, we consider one-sided-perfect $f$-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix in the method of Asadi, Culf, and May (ITCS 2025), we derive a lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.

quant-pharXiv:2609.24291•Sep 22, 2026•0 citations

A linear lower bound on the unbounded error probabilistic communication complexity

Jürgen Forster

Journal of Computer and System Sciences•Dec 1, 2002•189 citations
We study bounded-error randomization and majority operators in structural communication complexity. We give a communication-complexity formulation of Tarui's theorem and identify the bounded-error closure of weakly unbounded-error communication with a distributional perturbation of logarithmic margin complexity. Retaining the Boolean guarantee in Tarui's probabilistic polynomials yields the stronger inclusion PHcc⊆ZP⋅PPcc⊆BP⋅PPcc\mathsf{PH}^{\mathrm{cc}} \subseteq \mathsf{ZP}\mathbin{\cdot} \mathsf{PP}^{\mathrm{cc}} \subseteq \mathsf{BP}\mathbin{\cdot} \mathsf{PP}^{\mathrm{cc}}PHcc⊆ZP⋅PPcc⊆BP⋅PPcc. We also define a majority operator satisfying PP⋅Pcc=PPcc\mathsf{PP}\mathbin{\cdot} \mathsf{P}^{\mathrm{cc}} = \mathsf{PP}^{\mathrm{cc}}PP⋅Pcc=PPcc and use Sasaki's majority formula to prove that ⊕Pcc⊆PP⋅PPcc\mathord{\oplus}\mathsf{P}^{\mathrm{cc}} \subseteq \mathsf{PP}\mathbin{\cdot} \mathsf{PP}^{\mathrm{cc}}⊕Pcc⊆PP⋅PPcc. For the inner-product function modulo two, both the outer index and each inner protocol have logarithmic cost. Together with Forster's lower bound, this gives an explicit witness to the non-idempotence of the majority operator and to PP⋅PPcc⊈UPPcc\mathsf{PP}\mathbin{\cdot} \mathsf{PP}^{\mathrm{cc}} \not\subseteq \mathsf{UPP}^{\mathrm{cc}}PP⋅PPcc⊆UPPcc. Both the bounded-error closure and the two-level majority class are contained in PSPACEcc\mathsf{PSPACE}^{\mathrm{cc}}PSPACEcc.
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form F(x,y)=f(x1∧y1,…,xn∧yn), F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), F(x,y)=f(x1​∧y1​,…,xn​∧yn​), when the outer function fff is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function fff, the bounded-error quantum and classical deterministic communication complexities of the function f∘AND2f \circ \mathrm{AND}_2f∘AND2​ are polynomially related, up to polylogarithmic factors in nnn. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of fff. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.
Dual polynomials and communication complexity of XOR\textsf{XOR}XOR functions
We show a new duality between the polynomial margin complexity of fff and the discrepancy of the function f∘XORf \circ \textsf{XOR}f∘XOR, called an XOR\textsf{XOR}XOR function. Using this duality, we develop polynomial based techniques for understanding the bounded error (BPP\textsf{BPP}BPP) and the weakly-unbounded error (PP\textsf{PP}PP) communication complexities of XOR\textsf{XOR}XOR functions. We show the following. A weak form of an interesting conjecture of Zhang and Shi (Quantum Information and Computation, 2009) (The full conjecture has just been reported to be independently settled by Hatami and Qian (Arxiv, 2017). However, their techniques are quite different and are not known to yield many of the results we obtain here). Zhang and Shi assert that for symmetric functions f:{0,1}n→{−1,1}f : \{0, 1\}^n \rightarrow \{-1, 1\}f:{0,1}n→{−1,1}, the weakly unbounded-error complexity of f∘XORf \circ \textsf{XOR}f∘XOR is essentially characterized by the number of points iii in the set {0,1,…,n−2}\{0,1, \dots,n-2\}{0,1,…,n−2} for which Df(i)≠Df(i+2)D_f(i) \neq D_f(i+2)Df​(i)=Df​(i+2), where DfD_fDf​ is the predicate corresponding to fff. The number of such points is called the odd-even degree of fff. We show that the PP\textsf{PP}PP complexity of f∘XORf \circ \textsf{XOR}f∘XOR is Ω(k/log⁡(n/k))Ω(k/ \log(n/k))Ω(k/log(n/k)). We resolve a conjecture of a different Zhang characterizing the Threshold of Parity circuit size of symmetric functions in terms of their odd-even degree. We obtain a new proof of the exponential separation between PPcc\textsf{PP}^{cc}PPcc and UPPcc\textsf{UPP}^{cc}UPPcc via an XOR\textsf{XOR}XOR function. We provide a characterization of the approximate spectral norm of symmetric functions, affirming a conjecture of Ada et al. (APPROX-RANDOM, 2012) which has several consequences. Additionally, we prove strong UPP\textsf{UPP}UPP lower bounds for f∘XORf \circ \textsf{XOR}f∘XOR, when fff is symmetric and periodic with period O(n1/2−ε)O(n^{1/2-ε})O(n1/2−ε), for any constant ε>0ε> 0ε>0.
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions ppp and qqq over domains XXX and YYY, respectively. Their goal is to estimate Ex∼p, y∼q[f(x,y)] \mathbb{E}_{x \sim p,\, y \sim q}[f(x, y)] Ex∼p,y∼q​[f(x,y)] to within additive error ε\varepsilonε for a bounded function fff, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of fff and the error parameter ε\varepsilonε. The random sampling approach -- estimating the mean by averaging fff over O(1/ε2)O(1/\varepsilon^2)O(1/ε2) random samples -- requires O(R(f)/ε2)O(R(f)/\varepsilon^2)O(R(f)/ε2) total communication, where R(f)R(f)R(f) is the randomized communication complexity of fff. We design a new debiasing protocol which improves the dependence on 1/ε1/\varepsilon1/ε to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.
New lower bounds for CDS and fff-routing
Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case is fff-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC. Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and fff-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function. Second, we consider one-sided-perfect fff-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix in the method of Asadi, Culf, and May (ITCS 2025), we derive a lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.