Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error

We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ?, getting the optimal constant factors in the leading terms in various different models. The following are our results in the randomized model: 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. As a consequence we obtain a (log(n/?2) + 4)-cost private-coin communication protocol that computes the n-bit Equality function, to error ?. This improves upon the log(n/?3)+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 log log(1/?) + O(1). The following are our results in various quantum models: We exhibit a one-way protocol with log(n/?) + 4 qubits of communication for the n-bit Equality function, to error ?, that uses only pure states. This bound was implicitly already shown by Nayak [PhD thesis'99]. We give a near-matching lower bound: any ?-error one-way protocol for n-bit Equality that uses only pure states communicates at least log(n/?) log log(1/?) O(1) qubits. We exhibit a one-way protocol with log(v n/?) + 3 qubits of communication that uses mixed states. This is tight up to additive log log(1/?) + O(1), which follows from Alon's result. We exhibit a one-way entanglement-assisted protocol achieving error probability ? with ?log(1/?)? + 1 classical bits of communication and ?log(v n/?)? + 4 shared EPR-pairs between Alice and Bob. This matches the communication cost of the classical public coin protocol achieving the same error probability while improving upon the amount of prior entanglement that is needed for this protocol, which is ?log(n/?)? + O(1) shared EPR-pairs. Our upper bounds also yield upper bounds on the approximate rank, approximate nonnegative-rank, and approximate psd-rank of the Identity matrix. As a consequence we also obtain improved upper bounds on these measures for a function that was recently used to refute the randomized and quantum versions of the log-rank conjecture (Chattopadhyay, Mande and Sherif [J. ACM'20], Sinha and de Wolf [FOCS'19], Anshu, Boddu and Touchette [FOCS'19]).

• View at Publisher

Free Full Text ( Final Version , 797kb )