# Compressed Communication Complexity of _Hamming Distance_
###### Abstract  
We consider the communication complexity of the _Hamming distance_ of two strings. [PERSON] et al. [SPIRE 2018] considered the communication complexity of the longest common prefix (LCP) problem in the setting where the two parties have their strings in a compressed form, i.e., represented by the Lempel-Ziv 77 factorization (LZ77) with/without self-references. We present a randomized public-coin protocol for a joint computation of the _Hamming distance_ of two strings represented by LZ77 without self-references. Although our scheme is heavily based on [PERSON] et al. 's LCP protocol, our complexity analysis is original which uses [PERSON]'s C-factorization and [PERSON]'s AVL-grammar. As a byproduct, we also show that LZ77 with/without self-references are not monotonic in the sense that their sizes can increase by a factor of 4/3 when a prefix of the string is removed. communication complexity; _Hamming distance_; Lempel-Ziv compression Article Compressed Communication Complexity of Hamming Distance  
[PERSON], [PERSON],  
1. \(\mathcal{O}(\log z_{\ell}^{\prime}+\log\log\ell)\) communication rounds and \(\mathcal{O}(\log\ell)\) total bits of communication, or
2. \(\mathcal{O}(\log z_{\ell}^{\prime})\) communication rounds and \(\mathcal{O}(\log\ell+\log\log\log n)\) total bits of communication,  
where \(z_{\ell}^{\prime}\) denotes the size of the _self-referencing_ LZ77 factorization of the LCP \(A[1..\ell]\) and \(n=|A|\). In this paper, we consider the communication complexity of the _Hamming distance_ of two strings of equal length, which are represented in a compressed form. We present a randomized public-coin protocol for a joint computation of the _Hamming distance_ of two strings represented by _non-self-referencing_ LZ77, with \(O(d\log z)\) communication rounds and \(\mathcal{O}(d\log\ell_{\max})\) total bits of communication, where \(d\) is the _Hamming distance_ between \(A\) and \(B\), \(z\) is the size of the LZ77 factorization of string \(A\), and \(\ell_{\max}\) is the largest gap between two adjacent mismatching positions between \(A\) and \(B\) (if the first/last characters of \(A\) and \(B\) are equal, then we can add terminal symbols as \(\#A\$\) and \(\$B\#\) and subtract 2 from the computed distance). Although our scheme is heavily based on [PERSON] et al. 's LCP protocol, our complexity analysis is original which uses [PERSON]'s C-factorization [9] and [PERSON]'s AVL-grammar [10]. Furthermore, as a byproduct of our result for the _Hamming distance_ problem, we also show that LZ77 with/without self-references are _non-monotonic_. For a compression algorithm A let \(\mathsf{A}(S)\) denote the size of the compressed representation of string \(S\) by A. We say that compression algorithm A is _monotonic_ if \(\mathsf{A}(S[1..j])\leq\mathsf{A}(S)\) for any \(1\leq j<|S|\) and \(\mathsf{A}(S[i..|S|])\leq\mathsf{A}(S)\) for any \(1<i\leq|S|\), and we say it is _non-monotonic_ otherwise. It is clear that LZ77 with/without self-references satisfy the first property, however, to our knowledge the second property has not been studied for the LZ77 factorizations. We prove that LZ77 with/without self-references is _non-monotonic_ by giving a family of strings such that removing each prefix of length from 1 to \(\sqrt{n}\) increases the number of factors in the LZ77 factorization by a factor of \(4/3\), where \(n\) denotes the string length. We also show that in the worst-case the number of factors in the non-self-referencing LZ77 factorization of any suffix of any string \(S\) of length \(n\) can be larger than that of \(S\) by at most a factor of \(O(\log n)\). Monotonicity of compression algorithms and string repetitive measures has gained recent attention. [PERSON] and [PERSON] [11] showed that _Lempel-Ziv 78 compression_[12] is non-monotonic by showing that removing the first character of a string can increase the size of the compression by a factor of \(\Omega(\log n)\). The recently proposed repetitive measure called the _substring complexity_\(\delta\) is known to be monotonic [13].