English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We investigate the randomized and quantum communication complexities of thewell-studied Equality function with small error probability $\epsilon$, gettingoptimal 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 toprivate-coin protocols by incurring a small multiplicative error, at a smalladditive 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/\epsilon^2)+4)$-cost private-coincommunication protocol that computes the $n$-bit Equality function, to error$\epsilon$. This improves upon the $\log(n/\epsilon^3)+O(1)$ upper boundimplied by Newman's theorem, and matches the best known lower bound, whichfollows from Alon [Comb. Prob. Comput.'09], up to an additive$\log\log(1/\epsilon)+O(1)$.  In the quantum model,  1) we exhibit a one-way protocol of cost $\log(n/\epsilon)+4$, that uses onlypure states and computes the $n$-bit Equality function to error $\epsilon$.This bound was implicitly already shown by Nayak [PhD thesis'99].  2) We show that any $\epsilon$-error one-way protocol for $n$-bit Equalitythat uses only pure states communicates at least$\log(n/\epsilon)-\log\log(1/\epsilon)-O(1)$ qubits.  3) We exhibit a one-way protocol of cost $\log(\sqrt{n}/\epsilon)+3$, thatuses 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.  4) We study the number of EPR pairs required to be shared in anentanglement-assisted one-way protocol.  Our upper bounds also yield upper bounds on the approximate rank and relatedmeasures of the Identity matrix.

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