Compressed Communication Complexity of Hamming Distance
Compressed Communication Complexity of Hamming Distance
复制标题
DOI：
10.3390/a14040116
复制
发表时间：
2021-04-01
期刊：
影响因子：
2.3
通讯作者：
Takeda, Masayuki
中科院分区：
文献类型：
--
作者：
Mitsuya, Shiori;Nakashima, Yuto;Takeda, Masayuki
我们考虑了两个字符串的汉明距离的通信复杂度。Bille等人[SPIRE 2018]考虑了在双方以压缩形式拥有字符串的情况下最长公共前缀（LCP）问题的通信复杂性，即，由具有/不具有自引用的Lempel-Ziv 77因子分解（LZ 77）表示。我们提出了一个随机公共硬币协议，用于联合计算由LZ 77表示的两个字符串的汉明距离，而无需自引用。虽然我们的计划是严重的基础上Bille等人。的LCP协议，我们的复杂性分析是原创的，它使用了Crochemore的C-因子分解和Rytter的AVL-文法。作为一个副产品，我们还表明，LZ 77与/不自引用是不是单调的意义上说，它们的大小可以增加4/3的因素时，字符串的前缀被删除。
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. Although 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.