Communication complexity of XOR functions $f (x \oplus y)$ has attracted increasing attention in recent years, because of its connections to Fourier analysis, and its exhibition of exponential separations between classical and quantum communication complexities of total functions.However, the complexity of certain basic functions still seems elusive especially in the private-coin SMP model. In particular, an exponential gap exists between quantum upper and lower bounds for deciding whether $x$ and $y$ have Hamming distance at least $d$, despite the sequence of related efforts [GKdW04,HSZZ06, ZS09] since Yao asked it as an open question [Yao03]. In this paper we resolve this question by providing optimal randomized and quantum protocols. We then apply the result and show efficient protocols for all symmetric XOR functions and linear threshold functions, answering an open question in [LLZ11] and another in [MO10]. Finally,we consider matrix functions and show upper bounds for the matrix rank decision problem; the public-coin classical SMP result matches the quantum two-way lower bound in [SW12].
Motivated from data sketching applications, we aim at efficiency of computation as well as communication. Our protocols for matrix rank decision are computationally efficient in the classical setting, and other protocols are computationally efficient if Alice and Bob have quantum computers. The main techniques used in our protocols are compressed sensing, and the Bose-Chowla theorem from combinatorial number theory. To the best of our knowledge, this is the first time that these two techniques are applied to communication complexity, in which we believe that more applications could be found.