Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MING LAM LEUNG:
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

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 >>>




ISSN 1433-8092 | Imprint