{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T04:55:23Z","timestamp":1783572923136,"version":"3.55.0"},"reference-count":18,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,4,3]],"date-time":"2021-04-03T00:00:00Z","timestamp":1617408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18K18002, JP20H04141, JP18H04098"],"award-info":[{"award-number":["JP18K18002, JP20H04141, JP18H04098"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJPR1922"],"award-info":[{"award-number":["JPMJPR1922"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.\u2019s LCP protocol, our complexity analysis is original which uses Crochemore\u2019s C-factorization and Rytter\u2019s 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.<\/jats:p>","DOI":"10.3390\/a14040116","type":"journal-article","created":{"date-parts":[[2021,4,3]],"date-time":"2021-04-03T22:03:36Z","timestamp":1617487416000},"page":"116","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Compressed Communication Complexity of Hamming Distance"],"prefix":"10.3390","volume":"14","author":[{"given":"Shiori","family":"Mitsuya","sequence":"first","affiliation":[{"name":"Department of Informatics, Kyushu University, 744, Motooka, Nishiku, Fukuoka 819-0395, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6269-9353","authenticated-orcid":false,"given":"Yuto","family":"Nakashima","sequence":"additional","affiliation":[{"name":"Department of Informatics, Kyushu University, 744, Motooka, Nishiku, Fukuoka 819-0395, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1833-010X","authenticated-orcid":false,"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[{"name":"Department of Informatics, Kyushu University, 744, Motooka, Nishiku, Fukuoka 819-0395, Japan"},{"name":"PRESTO, Japan Science and Technology Agency, 4-1-8, Honcho, Kawaguchi, Saitama 332-0012, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6856-5185","authenticated-orcid":false,"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[{"name":"M&amp;D Data Science Center, Tokyo Medical and Dental University, Tokyo 101-0062, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6138-1607","authenticated-orcid":false,"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[{"name":"Department of Informatics, Kyushu University, 744, Motooka, Nishiku, Fukuoka 819-0395, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,4,3]]},"reference":[{"key":"ref_1","unstructured":"Yao, A.C. (\u20132, January 30). Some Complexity Questions Related to Distributive Computing (Preliminary Report). Proceedings of the Eleventh Annual ACM-SIAM Symposium onTheory of computing, Atlanta, Georgia."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.tcs.2012.06.012","article-title":"Space lower bounds for online pattern matching","volume":"483","author":"Clifford","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"104513","DOI":"10.1016\/j.ic.2019.104513","article-title":"Streaming k-mismatch with error correcting and applications","volume":"271","author":"Radoszewski","year":"2020","journal-title":"Inf. Comput."},{"key":"ref_4","unstructured":"Jalsenius, M., Porat, B., and Sach, B. (2013). Parameterized Matching in the Streaming Model. STACS, 400\u2013411."},{"key":"ref_5","unstructured":"Gawrychowski, P., and Starikovskaya, T. (2019, January 18\u201320). Streaming Dictionary Matching with Mismatches. Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), Pisa, Italy."},{"key":"ref_6","unstructured":"Gawrychowski, P., Radoszewski, J., and Starikovskaya, T. (2019, January 18\u201320). Quasi-Periodicity in Streams. Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), Pisa, Italy."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Bille, P., Ettienne, M.B., Grossi, R., G\u00f8rtz, I.L., and Rotenberg, E. (2018). Compressed Communication Complexity of Longest Common Prefixes. International Symposium on String Processing and Information Retrieval, Proceedings of the 25th International Symposium, SPIRE 2018, Lima, Peru, 9\u201311 October 2018, Springer.","DOI":"10.1007\/978-3-030-00479-8_7"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","first-page":"66","article-title":"Linear searching for a square in a word","volume":"24","author":"Crochemore","year":"1984","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","article-title":"Application of Lempel-Ziv factorization to the approximation of grammar-based compression","volume":"302","author":"Rytter","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Lagarde, G., and Perifel, S. (2018, January 7\u201310). Lempel-Ziv: A \u201cone-bit catastrophe\u201d but not a tragedy. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611975031.97"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Navarro, G., and Prezza, N. (2020). Towards a Definitive Measure of Repetitiveness. Latin American Symposium on Theoretical Informatics, Proceedings of the 14th Latin American Symposium, S\u00e3o Paulo, Brazil, 5\u20138 January 2020, Springer.","DOI":"10.1007\/978-3-030-61792-9_17"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","article-title":"Data compression via textual substitution","volume":"29","author":"Storer","year":"1982","journal-title":"J. ACM"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Kempa, D., and Prezza, N. (2018, January 25\u201329). At the roots of dictionary compression: string attractors. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, USA.","DOI":"10.1145\/3188745.3188814"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.tcs.2020.11.006","article-title":"A combinatorial view on string attractors","volume":"850","author":"Mantaci","year":"2021","journal-title":"Theor. Comput. Sci."},{"key":"ref_17","first-page":"1259","article-title":"An algorithm for the organization of information","volume":"3","author":"Landis","year":"1962","journal-title":"Sov. Math. Dokl."},{"key":"ref_18","unstructured":"Knuth, D.E. (1998). The Art of Computer Programming, Addison-Wesley. [2nd ed.]."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/116\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:33:46Z","timestamp":1760362426000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,3]]},"references-count":18,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,4]]}},"alternative-id":["a14040116"],"URL":"https:\/\/doi.org\/10.3390\/a14040116","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,3]]}}}