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.
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⊕y∣), for any x,y∈{0,1}n, where ∣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, the error-bounded randomized and quantum communication complexities are Θ(r0+r1), where r0 and r1 are the minimum integers such that r0,r1≤n/2 and S(k)=S(k+2) for all k∈[r0,n−r1).
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⊕y∣), for any x,y∈{0,1}n, where ∣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 Θ(r0+r1), where r0 and r1 are the minimum integers such that r0,r1≤n/2 and S(k)=S(k+2) for all k∈[r0,n−r1).
We prove an essentially tight lower bound on the unbounded-error communication complexity of every symmetric function, i.e., f(x,y)=D(|x∧y|), where D: {0,1,…,n}→{0,1} is a given predicate and x,y range over {0,1} n . Specifically, we show that the communication complexity of f is between Θ(k/log5 n) and Θ(k logn), where k is the number of value changes of D in {0,1,…, n}. Prior to this work, the problem was solved only for the parity predicate D (Forster 2001). Our proof is built around two new ideas. First, we show that a predicate D gives rise to a rapidly mixing random walk on ℤ 2 , which allows us to reduce the problem to communication lower bounds for “typical” predicates. Second, we use Paturi’s approximation lower bounds (1992), suitably generalized here to clusters of real nodes in [0,n] and interpreted in their dual form, to prove that a typical predicate behaves analogous to the parity predicate with respect to a smooth distribution on the inputs.
Boolean function F(x,y) for x,y∈{0,1}n is an XOR function if F(x,y)=f(x⊕y) for some function f on n input bits, where ⊕ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing Fourier analytic technique. For total XOR functions it is known that deterministic communication complexity of F is closely related to parity decision tree complexity of f. Montanaro and Osbourne (2009) observed that one-sided communication complexity Dcc→(F) of F is exactly equal to nonadaptive parity decision tree complexity NADT⊕(f) of f. Hatami et al. (2018) showed that unrestricted communication complexity of F is polynomially related to parity decision tree complexity of f. We initiate the studies of a similar connection for partial functions. We show that in case of one-sided communication complexity whether these measures are equal, depends on the number of undefined inputs of f. On the one hand, if Dcc→(F)=t and f is undefined on at most O(n−t2n−t), then NADT⊕(f)=t. On the other hand, for a wide range of values of Dcc→(F) and NADT⊕(f) (from constant to n−2) we provide partial functions for which Dcc→(F)<NADT⊕(f). In particular, we provide a function with an exponential gap between the two measures. Our separation results translate to the case of two-sided communication complexity as well, in particular showing that the result of Hatami et al. (2018) cannot be generalized to partial functions. Previous results for total functions heavily rely on Boolean Fourier analysis and the technique does not translate to partial functions. For the proofs of our results we build a linear algebraic framework instead. Separation results are proved through the reduction to covering codes.
Bri\et et al. showed that an efficient communication protocol implies a reliable XOR game protocol. In this work, we improve this relationship, and obtain a nontrivial lower bound 2log3≈3.1699 of XOR-amortized communication complexity of the equality function. The proof uses an elegant idea of Paw\l owski et al. in a paper on information causality. Although the improvement of a lower bound of a communication complexity is at most a factor 2, all arguments and proofs in this work are quite simple and intuitive.