Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-157 | 1st June 2024 11:57

One-Way Communication Complexity of Partial XOR Functions

RSS-Feed




Revision #1
Authors: Vladimir Podolskii, Dmitrii Sluch
Accepted on: 1st June 2024 11:57
Downloads: 91
Keywords: 


Abstract:

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 $\mathrm{D_{cc}^{\rightarrow}}(F)$ of $F$ is exactly equal to nonadaptive parity decision tree complexity $\mathrm{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$. More precisely, if $\mathrm{D_{cc}^{\rightarrow}}(F)=t$ and $f$ is undefined on at most $O\left(\frac{2^{n-t}}{\sqrt{n-t}}\right)$, then $\mathrm{NADT^{\oplus}}(f)=t$.
We provide improved bounds on the number of undefined inputs for $t=1,2$. On the other end of the spectrum, we observe that measures are equal for any partial function $f$ satisfying $\mathrm{NADT^{\oplus}}(f) \geq n-1$.

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 $\mathrm{D_{cc}^{\rightarrow}}(F)$ and $\mathrm{NADT^{\oplus}}(f)$ (from constant to $n-2$) we provide partial functions (with more than $\Omega\left(\frac{2^{n-t}}{\sqrt{n-t}}\right)$ undefined inputs) for which $\mathrm{D_{cc}^{\rightarrow}}(F) < \mathrm{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 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.


Paper:

TR23-157 | 31st October 2023 19:55

One-Way Communication Complexity of Partial XOR Functions





TR23-157
Authors: Vladimir Podolskii, Dmitrii Sluch
Publication: 31st October 2023 23:31
Downloads: 343
Keywords: 


Abstract:

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 $\mathrm{D_{cc}^{\rightarrow}}(F)$ of $F$ is exactly equal to nonadaptive parity decision tree complexity $\mathrm{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$. More precisely, if $\mathrm{D_{cc}^{\rightarrow}}(F)=t$ and $f$ is undefined on at most $O\left(\frac{2^{n-t}}{\sqrt{n-t}}\right)$, then $\mathrm{NADT^{\oplus}}(f)=t$.
We provide improved bounds on the number of undefined inputs for $t=1,2$. On the other end of the spectrum, we observe that measures are equal for any partial function $f$ satisfying $\mathrm{NADT^{\oplus}}(f) \geq n-1$.

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 $\mathrm{D_{cc}^{\rightarrow}}(F)$ and $\mathrm{NADT^{\oplus}}(f)$ (from constant to $n-2$) we provide partial functions (with more than $\Omega\left(\frac{2^{n-t}}{\sqrt{n-t}}\right)$ undefined inputs) for which $\mathrm{D_{cc}^{\rightarrow}}(F) < \mathrm{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 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.



ISSN 1433-8092 | Imprint