All reports by Author Ming Lam Leung:

__
TR11-011
| 1st February 2011
__

Ming Lam Leung, Yang Li, Shengyu Zhang#### Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models

Ming Lam Leung, Yang Li, Shengyu Zhang

We study the communication complexity of symmetric XOR functions, namely functions $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus y|)$ for some predicate $D: \{0,1,...,n\} \rightarrow \{0,1\}$, where $|x\oplus y|$ is the Hamming weight of the bitwise XOR of $x$ and $y$. We give a public-coin ... more >>>