The Unbounded-Error Communication Complexity of symmetric XOR functions
classification
💻 cs.CC
keywords
communicationcomplexityfunctionssymmetricunbounded-errorconjecturedetermineearlier
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.