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 consider the communication complexity of the Hamming distance of twostrings. Bille et al. [SPIRE 2018] considered the communication complexity ofthe longest common prefix (LCP) problem in the setting where the two partieshave their strings in a compressed form, i.e., represented by the Lempel-Ziv 77factorization (LZ77) with/without self-references. We present a randomizedpublic-coin protocol for a joint computation of the Hamming distance of twostrings represented by LZ77 without self-references. While our scheme isheavily based on Bille et al.'s LCP protocol, our complexity analysis isoriginal which uses Crochemore's C-factorization and Rytter's AVL-grammar. As abyproduct, we also show that LZ77 with/without self-references are notmonotonic in the sense that their sizes can increase by a factor of 4/3 when aprefix of the string is removed.

Compressed Communication Complexity of Hamming Distance