We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(\log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. A similar result was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06]. Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88].We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(\log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. A similar result was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06]. Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88].

arXiv:quant-ph/0607173Jul 25, 20069 citations

Exponential separation of quantum and classical communication complexity

Ran Raz

Communication complexity has become a central completity model.In that model, we count the amount of communication bits needed between two parties in order to solve certain computational problems.We show that for certain communication complezity problems quantum communication protocols are exponentially faster than classical ores.More explicitly, we give an example for a communication complexity relation (0~ promise problem) P such that: 1) The quantum communication complexity of P is O(log m). 2) The classical probabilistic communication complexity of P is Q(m'l'/ logm).(where m is the length of the inputs).This gives an ezponential gap between quantum communication complexity and classical probabilistic communication complexity.Only a quadratic gap was previously known.Our problem P is of geometrical nature, and is a finite precision variation of the following problem: Player I gets as input a unit vector z E R" and two orthogonal subspaces MO, MI c R". Player II gets as input an orthogonal matrixT : R" + R".Their goal is to answer 0 if T(x) E MO and 1 if T(x) E M,, (and any an~luer in any other case).We give an almost tight analysis for the quantum communication complexity and for the classical-probabilistic communication complexity of this problem.Communication complexity has become a central completity model.In that model, we count the amount of communication bits needed between two parties in order to solve certain computational problems.We show that for certain communication complezity problems quantum communication protocols are exponentially faster than classical ores.More explicitly, we give an example for a communication complexity relation (0~ promise problem) P such that: 1) The quantum communication complexity of P is O(log m). 2) The classical probabilistic communication complexity of P is Q(m'l'/ logm).(where m is the length of the inputs).This gives an ezponential gap between quantum communication complexity and classical probabilistic communication complexity.Only a quadratic gap was previously known.Our problem P is of geometrical nature, and is a finite precision variation of the following problem: Player I gets as input a unit vector z E R" and two orthogonal subspaces MO, MI c R". Player II gets as input an orthogonal matrixT : R" + R".Their goal is to answer 0 if T(x) E MO and 1 if T(x) E M,, (and any an~luer in any other case).We give an almost tight analysis for the quantum communication complexity and for the classical-probabilistic communication complexity of this problem.

ACM Symposium on Theory of Computing (STOC)May 1, 1999222 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

Composition Theorems in Communication Complexity

Troy Lee, Shengyu Zhang

arXiv:1003.1443Lecture notes in computer scienceJan 1, 201033 citations

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.