Abstract
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ε, getting optimal constant factors in the leading terms in a number of different models. In the randomized model, 1) we give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error, at a small additive cost. This is an improvement over Newman's theorem [Inf. Proc. Let.'91] in the dependence on the error parameter. 2) Using this we obtain a (log(n/ε²)+4)-cost private-coin communication protocol that computes the n-bit Equality function, to error ε. This improves upon the log(n/ε³)+O(1) upper bound implied by Newman's theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.'09], up to an additive loglog(1/ε)+O(1). In the quantum model, 1) we exhibit a one-way protocol of cost log(n/ε)+4, that uses only pure states and computes the n-bit Equality function to error ε. This bound was implicitly already shown by Nayak [PhD thesis'99]. 2) We show that any ε-error one-way protocol for n-bit Equality that uses only pure states communicates at least log(n/ε)-loglog(1/ε)-O(1) qubits. 3) We exhibit a one-way protocol of cost log(√n/ε)+3, that uses mixed states and computes the n-bit Equality function to error ε. This is also tight up to an additive loglog(1/ε)+O(1), which follows from Alon's result. 4) We study the number of EPR pairs required to be shared in an entanglement-assisted one-way protocol. Our upper bounds also yield upper bounds on the approximate rank and related measures of the Identity matrix.