Communication complexities of symmetric XOR functions  (pp0255-0263)
          Zhiqiang Zhang and Yaoyun Shi
          doi: https://doi.org/10.26421/QIC9.3-4-5
Abstracts: We call F : {0, 1}^n × {0, 1}^n → {0, 1} a symmetric XOR function if for a function S : {0, 1, ..., n} → {0, 1}, F(x, y) = S(|x X y|), for any x, y belong to {0, 1}^n, where |x X y| is the Hamming weight of the bit-wise XOR of x and y. We show that for any such function, (a) the deterministic communication complexity is always Θ(n) except for four simple functions that have a constant complexity, and (b) up to a polylog factor, both the error-bounded randomized complexity and quantum communication with entanglement complexity are Θ(r_0 + r_1), where r_0 and r_1 are the minimum integers such that r_0, r_1 ≤ n/2 and S(k) = S(k + 2) for all k belong to [r_0, n − r_1).
Key words: communication complexity, XOR functions, quantum communication.