ECCC-Report TR11-011https://eccc.weizmann.ac.il/report/2011/011Comments and Revisions published for TR11-011en-usTue, 01 Feb 2011 12:32:43 +0200
Paper TR11-011
| Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models |
Ming Lam Leung,
Yang Li,
Shengyu Zhang
https://eccc.weizmann.ac.il/report/2011/011We 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 quantum and 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.Tue, 01 Feb 2011 12:32:43 +0200https://eccc.weizmann.ac.il/report/2011/011