Computer Science – Computational Complexity
Scientific paper
2011-01-24
TAMC11', Proceedings of the 8th Theory and Applications of Models of Computation Lecture Notes in Computer Science, 2011, Volu
Computer Science
Computational Complexity
Scientific paper
10.1007/978-3-642-20877-5_39
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 randomized protocol in the Simultaneous Message Passing (SMP) model, with the communication cost matching the known lower bound for the \emph{quantum} and \emph{two-way} model up to a logarithm factor. As a corollary, this closes a quadratic gap between quantum lower bound and randomized upper bound for the one-way model, answering an open question raised in Shi and Zhang \cite{SZ09}.
Leung Ming Lam
Li Yang
Zhang Shengyu
No associations
LandOfFree
Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models 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 Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-637479