ECCC-Report TR21-113https://eccc.weizmann.ac.il/report/2021/113Comments and Revisions published for TR21-113en-usSun, 01 Aug 2021 09:31:27 +0300
Paper TR21-113
| Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error |
Nikhil Mande,
Ronald de Wolf
https://eccc.weizmann.ac.il/report/2021/113We 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]).Sun, 01 Aug 2021 09:31:27 +0300https://eccc.weizmann.ac.il/report/2021/113