The Unbounded-Error Communication Complexity of symmetric XOR functions
arXiv:1704.00777
Abstract
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.