Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-113 | 25th July 2021 23:08

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

RSS-Feed




TR21-113
Authors: Nikhil Mande, Ronald de Wolf
Publication: 1st August 2021 09:31
Downloads: 582
Keywords: 


Abstract:

We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $\epsilon$, getting the optimal constant factors in the leading terms in a number of different models.

The following are our results 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) As a consequence we obtain a $(\log(n/\epsilon^2) + 4)$-cost private-coin communication protocol that computes the $n$-bit Equality function, to error $\epsilon$. This improves upon the $\log(n/\epsilon^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/\epsilon) + O(1)$.

The following are our results in the quantum model:

1) We exhibit a one-way protocol with $\log(n/\epsilon) + 4$ qubits of communication, that uses only pure states and computes the $n$-bit Equality function to error $\epsilon$. This bound was implicitly already shown by Nayak [PhD thesis'99].

2) We give a near-matching lower bound, showing that any $\epsilon$-error one-way protocol for $n$-bit Equality that uses only pure states communicates at least $\log(n/\epsilon) - \log\log(1/\epsilon) - O(1)$ qubits.

3) We exhibit a one-way protocol with $\log(\sqrt{n}/\epsilon) + 3$ qubits of communication, that uses mixed states and computes the $n$-bit Equality function to error $\epsilon$. This is also tight up to an additive $\log\log(1/\epsilon) + O(1)$, which follows from Alon's result.

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 the distributed SINK function, which 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]).



ISSN 1433-8092 | Imprint