Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models

Abstract. We study the communication complexity of symmetric XOR functions, namely functions f: {0, 1}n × {0, 1}n → {0, 1} that can be formulated as f(x, y) = D(|x ⊕ y|) for some predicate D: {0, 1,..., n} → {0, 1}, where |x ⊕ 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 the previous quantum lower bound and the randomized upper bound in the one-way model. This answers an open question raised in Shi and Zhang [SZ09], and disqualifies the problem from being a candidate to separate randomized and quantum one-way communication complexities.