Unbounded Error Communication Complexity of XOR Functions

We consider the unbounded error communication complexity of XOR functions, i.e. those of the form f of XOR, where f is an arbitrary boolean function on n bits. An interesting conjecture of Zhang and Shi [ZS'09] asserts that for symmetric f, the unbounded error complexity is essentially characterized by the number of points in {0,..., n-2} for which D(i) doesn't equal D(i + 2), where D is the predicate corresponding to f.

We make progress on the above conjecture by proving strong lower bounds when f is periodic with period n^{1/2 - epsilon} for any constant epsilon > 0. More precisely, we show that every such XOR function has unbounded error complexity n^{Omega(1)}, unless f is a constant or parity or its complement, in which case the complexity is just O(1). As a direct consequence of this, we derive new exponential lower bounds on the size of depth-2 threshold circuits computing such XOR functions (this is based on joint work with Arkadev Chattopadhyay).