# Compressed Communication Complexity of _Hamming Distance_
## 2 Preliminaries
### Lempel-Ziv 77 Factorizations  
Of many versions of Lempel-Ziv 77 factorization [8] which divide a given string in a greedy left-to-right manner, the main tool we use is the non-self-referencing LZ77, which is formally defined as follows:  
**Definition 1** (Non-self-referencing LZ77 factorization). : _The non-self-referencing LZ77 factorization of string \(S\), denoted \(\mathsf{LZN}(S)\), is a factorization \(S=f_{1}\cdots f_{\mathsf{Zn}}\) that satisfies the following: Let \(u_{i}\) denote the beginning position of each factor \(f_{i}\) in the factorization \(f_{1}\cdots f_{\mathsf{Zn}}\), that is, \(u_{i}=|f_{1}\cdots f_{i-1}|+1\). (1) If \(i>1\) and \(\max_{1\leq j<u_{i}}\{\operatorname{lcp}(S[u_{i-1}],S[j..u_{i}-1])\}\geq 1\), then for any position \(s_{i}\in\operatorname*{arg\,max}_{1\leq j<u_{i}}\operatorname{lcp}(S[u_{i-1} ],S[j..u_{i}-1])\) in \(S\), let \(p_{i}=\operatorname{lcp}(S[u_{i}..],S[s_{i}..u_{i}-1])\). (2) Otherwise, let \(p_{i}=0\). Then, \(f_{i}=S[s_{i}..u_{i}+p_{i}]\) for each \(1\leq i\leq\mathsf{zn}\)._  
Intuitively, each factor \(f_{i}\) in \(\mathsf{LZN}(S)\) is either a fresh letter, or the shortest prefix of \(f_{i}\cdots f_{\mathsf{zn}}\) that does not have a previous occurrence in \(f_{1}\ldots f_{i-1}\). This means that self-referencing is _not_ allowed in \(\mathsf{LZN}(S)\), namely no previous occurrences \(S[s_{i}..s_{i}+p_{i}]\) of each factor \(f_{i}\) can overlap with itself. The _size_\(\mathsf{zn}(S)\) of \(\mathsf{LZN}(S)\) is the number \(\mathsf{zn}\) of factors in \(\mathsf{LZN}(S)\). We encode each factor \(f_{i}\) by a triple \((s_{i},p_{i},\alpha_{i})\in([1..n]\times[1..n]\times\Sigma)\), where \(s_{i}\) is the left-most previous occurrence of \(f_{i}\), \(p_{i}\) is the length of \(f_{i}\), and \(\alpha_{i}\) is the last character of \(f_{i}\). **Example 1**. : For \(S=\mathtt{abaababaabaabaabaabaabb},\mathsf{LZS}(S)=\mathtt{a}\mid\mathtt{b} \mid\mathtt{aa}\mid\mathtt{bab}\mid\mathtt{aabaa}\mid\mathtt{baabab}\mid \mathtt{aabb}\mid\mathtt{aabb}\mid\mathtt{and}\) it can be represented as \((0,0,\mathtt{a}),(0,0,\mathtt{b}),(1,2,\mathtt{a}),(2,3,\mathtt{b}),(3,5, \mathtt{a}),(7,7,\mathtt{b}),\)\((3,4,\mathtt{b})\). The size of \(\mathsf{LZS}(S)\) is 7. The self-referencing counterpart is defined as follows:  
**Definition 2** (Self-referencing LZ77 factorization). : _The self-referencing LZ77 factorization of string \(S\), denoted \(\mathsf{LZS}(S)\), is a factorization \(S=g_{1}\cdots g_{\mathsf{zs}}\) that satisfies the following: Let \(v_{i}\) denote the beginning position of each factor \(g_{i}\) in the factorization \(g_{1}\cdots g_{\mathsf{zs}}\), that is, \(v_{i}=|g_{1}\cdots g_{i-1}|+1\). (1) If \(i>1\) and \(\max_{1\leq j<v_{i}}\{\operatorname{lcp}(S[v_{i}..],S[j..])\}\geq 1\), then for any position \(t_{i}\in\operatorname*{arg\,max}_{1\leq j<v_{i}}\{S[v_{i}..],S[j..]\}\) in \(S\), let \(q_{i}=\operatorname{lcp}(S[v_{i}..],S[t_{i}..])\). (2) Otherwise, let \(q_{i}=0\). Then, \(g_{i}=S[v_{i}..v_{i}+q_{i}]\) for each \(1\leq i\leq\mathsf{zs}\)._  
Intuitively, each factor \(g_{i}\) of \(\mathsf{LZS}(S)\) is either a fresh letter, or the shortest prefix of \(g_{i}\cdots g_{\mathsf{zs}}\) that does not have a previous occurrence beginning in \(g_{1}\cdots g_{i-1}\). This means that self-referencing is allowed in \(\mathsf{LZS}(S)\), namely the left-most previous occurrence with smallest \(t_{i}\) of each factor \(g_{i}\) may overlap with itself. The _size_\(\mathsf{zs}(S)\) of \(\mathsf{LZS}(S)\) is the number \(\mathsf{zs}\) of factors in \(\mathsf{LZS}(S)\). Likewise, we encode each factor \(g_{i}\) by a triple \((t_{i},q_{i},\beta_{i})\in([1..n]\times[1..n]\times\Sigma)\), where \(t_{i}\) is the left-most previous occurrence of \(g_{i}\), \(q_{i}\) is the length of \(g_{i}\), and \(\beta_{i}\) is the last character of \(g_{i}\). **Example 2**.