Quantum Information and Computation

Communication complexities of symmetric XOR functions

ZhangZhiqiang, ShiYaoyun

Published Mar 1, 2009• 2 citations

Abstract

We call F : {0, 1}n × {0, 1}n → {0, 1} a symmetric XOR function if for a functionS : {0, 1, ..., n} → {0, 1}, F(x, y) = S(|x⊕y|), for any x, y ∈ {0, 1}n, where |x⊕y| is theHamming weight of the bit...

DOI: 10.5555/2011781.2011786

Related papers

Communication complexities of symmetric XOR functions

Z.-Q. Zhang, Y.-Y. Shi

Quantum Information and ComputationMar 1, 200939 citations

Communication Complexities of XOR functions

Yaoyun Shi, Zhiqiang Zhang

arXiv:0808.1762Aug 13, 200811 citations

The Unbounded-Error Communication Complexity of symmetric XOR functions

Hamed Hatami, Yingjie Qian

Settling a conjecture of Shi and Zhang, we determine the unbounded-error communication complexity of the symmetric XOR functions up to a poly-logarithmic factor. Our proof is by a simple reduction to an earlier result of Sherstov.

arXiv:1704.00777Apr 3, 20174 citations

On the communication complexity of XOR functions

Ashley Montanaro, Tobias Osborne

arXiv:0909.3392Sep 18, 200944 citations

One-Way Communication Complexity of Partial XOR Functions

Vladimir V. Podolskii, Dmitrii Sluch

Leibniz international proceedings in informaticsJan 1, 20240 citations

One-Way Communication Complexity of Partial XOR Functions

Vladimir V. Podolskii, Sluch, Dmitrii

arXiv:2310.20606Oct 31, 20230 citations

Quantum Information and Computation

Communication complexities of symmetric XOR functions

ZhangZhiqiang, ShiYaoyun

Published Mar 1, 2009• 2 citations

Publisher

Abstract

DOI: 10.5555/2011781.2011786

Related papers

Communication complexities of symmetric XOR functions

Z.-Q. Zhang, Y.-Y. Shi

We call $F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}$ a symmetric XOR function if for a function $S:\{0, 1, ..., n\}\to\{0, 1\}$ , $F(x, y)=S(|x\oplus y|)$ , for any $x, y\in\{0, 1\}^n$ , where $|x\oplus y|$ is the Hamming weight of the bit-wise XOR of $x$ and $y$ . We show that for any such function, (a) the deterministic communication complexity is always $\Theta(n)$ except for four simple functions that have a constant complexity, and (b) up to a polylog factor, both the error-bounded randomized complexity and quantum communication with entanglement complexity are $\Theta(r_0+r_1)$ , where $r_0$ and $r_1$ are the minimum integers such that $r_0, r_1\leq n/2$ and $S(k)=S(k+2)$ for all $k\in[r_0, n-r_1)$ .We call $F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}$ a symmetric XOR function if for a function $S:\{0, 1, ..., n\}\to\{0, 1\}$, $F(x, y)=S(|x\oplus y|)$, for any $x, y\in\{0, 1\}^n$, where $|x\oplus y|$ is the Hamming weight of the bit-wise XOR of $x$ and $y$. We show that for any such function, (a) the deterministic communication complexity is always $\Theta(n)$ except for four simple functions that have a constant complexity, and (b) up to a polylog factor, both the error-bounded randomized complexity and quantum communication with entanglement complexity are $\Theta(r_0+r_1)$, where $r_0$ and $r_1$ are the minimum integers such that $r_0, r_1\leq n/2$ and $S(k)=S(k+2)$ for all $k\in[r_0, n-r_1)$.

Quantum Information and ComputationMar 1, 200939 citations

Communication Complexities of XOR functions

Yaoyun Shi, Zhiqiang Zhang

We call $F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}$ a symmetric XOR function if for a function $S:\{0, 1, ..., n\}\to\{0, 1\}$ , $F(x, y)=S(|x\oplus y|)$ , for any $x, y\in\{0, 1\}^n$ , where $|x\oplus y|$ is the Hamming weight of the bit-wise XOR of $x$ and $y$ . We show that for any such function, (a) the deterministic communication complexity is always $Θ(n)$ except for four simple functions that have a constant complexity, and (b) up to a polylog factor, the error-bounded randomized and quantum communication complexities are $Θ(r_0+r_1)$ , where $r_0$ and $r_1$ are the minimum integers such that $r_0, r_1\leq n/2$ and $S(k)=S(k+2)$ for all $k\in[r_0, n-r_1)$ .We call $F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}$ a symmetric XOR function if for a function $S:\{0, 1, ..., n\}\to\{0, 1\}$, $F(x, y)=S(|x\oplus y|)$, for any $x, y\in\{0, 1\}^n$, where $|x\oplus y|$ is the Hamming weight of the bit-wise XOR of $x$ and $y$. We show that for any such function, (a) the deterministic communication complexity is always $Θ(n)$ except for four simple functions that have a constant complexity, and (b) up to a polylog factor, the error-bounded randomized and quantum communication complexities are $Θ(r_0+r_1)$, where $r_0$ and $r_1$ are the minimum integers such that $r_0, r_1\leq n/2$ and $S(k)=S(k+2)$ for all $k\in[r_0, n-r_1)$.

arXiv:0808.1762Aug 13, 200811 citations

The Unbounded-Error Communication Complexity of symmetric XOR functions

Hamed Hatami, Yingjie Qian

arXiv:1704.00777Apr 3, 20174 citations

On the communication complexity of XOR functions

Ashley Montanaro, Tobias Osborne

An XOR function is a function of the form g(x,y) = f(x + y), for some boolean function f on n bits. We study the quantum and classical communication complexity of XOR functions. In the case of exact protocols, we completely characterise one-way communication complexity for all f. We also show that, when f is monotone, g's quantum and classical complexities are quadratically related, and that when f is a linear threshold function, g's quantum complexity is Theta(n). More generally, we make a structural conjecture about the Fourier spectra of boolean functions which, if true, would imply that the quantum and classical exact communication complexities of all XOR functions are asymptotically equivalent. We give two randomised classical protocols for general XOR functions which are efficient for certain functions, and a third protocol for linear threshold functions with high margin. These protocols operate in the symmetric message passing model with shared randomness.An XOR function is a function of the form g(x,y) = f(x + y), for some boolean function f on n bits. We study the quantum and classical communication complexity of XOR functions. In the case of exact protocols, we completely characterise one-way communication complexity for all f. We also show that, when f is monotone, g's quantum and classical complexities are quadratically related, and that when f is a linear threshold function, g's quantum complexity is Theta(n). More generally, we make a structural conjecture about the Fourier spectra of boolean functions which, if true, would imply that the quantum and classical exact communication complexities of all XOR functions are asymptotically equivalent. We give two randomised classical protocols for general XOR functions which are efficient for certain functions, and a third protocol for linear threshold functions with high margin. These protocols operate in the symmetric message passing model with shared randomness.

arXiv:0909.3392Sep 18, 200944 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

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

We call

F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}

a symmetric XOR function if for a function

S:\{0, 1, ..., n\}\to\{0, 1\}

F(x, y)=S(|x\oplus y|)

, for any

x, y\in\{0, 1\}^n

, where

|x\oplus y|

is the Hamming weight of the bit-wise XOR of

x

and

y

. We show that for any such function, (a) the deterministic communication complexity is always

\Theta(n)

except for four simple functions that have a constant complexity, and (b) up to a polylog factor, both the error-bounded randomized complexity and quantum communication with entanglement complexity are

\Theta(r_0+r_1)

, where

r_0

and

r_1

are the minimum integers such that

r_0, r_1\leq n/2

and

S(k)=S(k+2)

for all

k\in[r_0, n-r_1)

We call

F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}

a symmetric XOR function if for a function

S:\{0, 1, ..., n\}\to\{0, 1\}

F(x, y)=S(|x\oplus y|)

, for any

x, y\in\{0, 1\}^n

, where

|x\oplus y|

is the Hamming weight of the bit-wise XOR of

x

and

y

. We show that for any such function, (a) the deterministic communication complexity is always

Θ(n)

except for four simple functions that have a constant complexity, and (b) up to a polylog factor, the error-bounded randomized and quantum communication complexities are

Θ(r_0+r_1)

, where

r_0

and

r_1

are the minimum integers such that

r_0, r_1\leq n/2

and

S(k)=S(k+2)

for all

k\in[r_0, n-r_1)

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.