Tight bounds on the randomized 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\times \{0,1{\}}^n\to \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus y|)$ for some predicate $D:\{0,1,...,n\}\to \{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}.

References in corpus (4)

• The Communication Complexity of the Hamming Distance Problem
• Quantum Communication Cannot Simulate a Public Coin
• Composition theorems in communication complexity
• Communication Complexities of XOR functions

Cited by in corpus (4)

• Fourier sparsity, spectral norm, and the Log-rank conjecture
• Recent advances on the log-rank conjecture in communication complexity
• Linear Sketching over ${\mathbb{F}}_2$
• Approximate ${\mathbb{F}}_2$-Sketching of Valuation Functions