Communication Complexities of XOR functions

Details Communication Complexities of XOR functions Communication Complexities of XOR functions

2008-08-13

arxiv.org/abs/0808.1762v2

Physics

Quantum Physics

9 pages

Scientific paper

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, the error-bounded randomized and quantum communication complexities 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)$.

Affiliated with

Also associated with

No associations

Rating

Communication Complexities of XOR functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Communication Complexities of XOR functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communication Complexities of XOR functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-386217