  We consider the communication complexity of the Hamming distance of two
strings. Bille 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. While our scheme is
heavily based on Bille et al.'s LCP protocol, our complexity analysis is
original which uses Crochemore's C-factorization and Rytter'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.
