The Unbounded-Error Communication Complexity of symmetric XOR functions
Hamed Hatami, Yingjie Qian · arXiv (Cornell University) · 2017
Settling a conjecture of Shi and Zhang, we determine the unbounded-error communication complexity of the symmetric XOR functions up to a poly-logarithmic factor. Our proof is by a simple reduction to an earlier result of Sherstov.