{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T12:50:34Z","timestamp":1760014234408,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649604","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1758-1768","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Communication Complexity of Approximate Pattern Matching"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":false,"given":"Tomasz","family":"Kociumaka","sequence":"first","affiliation":[{"name":"Max Planck Institute for Informatics, Saarbr\u00fccken, Germany \/ Saarland Informatics Campus, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-7028-2595","authenticated-orcid":false,"given":"Jakob","family":"Nogler","sequence":"additional","affiliation":[{"name":"ETH Zurich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6482-8478","authenticated-orcid":false,"given":"Philip","family":"Wellnitz","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarbr\u00fccken, Germany \/ Saarland Informatics Campus, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00061"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-022-01092-X"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.2002.1826"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2020.8"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053128"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2023.10"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.22"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/130936889"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456807"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.69"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00135"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2020.07.003"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2022.35"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00095"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00072"},{"key":"e_1_3_2_1_17_1","volume-title":"41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024 (LIPIcs). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik. arxiv:2402","author":"Charalampopoulos Panagiotis","year":"2024","unstructured":"Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Wale\u0144, and Wiktor Zuba. 2024. Approximate Circular Pattern Matching under Edit Distance. In 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024 (LIPIcs). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik. arxiv:2402.14550."},{"key":"e_1_3_2_1_18_1","unstructured":"Andrew M. Childs Robin Kothari Matt Kovacs-Deak Aarthi Sundaram and Daochen Wang. 2022. Quantum divide and conquer. arXiv:2210.06419."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.68"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700370527"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0174934-9"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-022-01066-Z"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45030-3_8"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.11"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00070"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00010-8"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch186"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00090"},{"key":"e_1_3_2_1_29_1","volume-title":"Almost Linear Size Edit Distance Sketch. In 56th Annual ACM Symposium on the Theory of Computing; STOC","author":"Kouck\u00fd Michal","year":"2024","unstructured":"Michal Kouck\u00fd and Michael Saks. 2024. Almost Linear Size Edit Distance Sketch. In 56th Annual ACM Symposium on the Theory of Computing; STOC 2024."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90045-1"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90010-2"},{"key":"e_1_3_2_1_32_1","first-page":"845","article-title":"Binary codes capable of correcting deletions, insertions and reversals","volume":"163","author":"Levenshtein Vladimir Iosifovich","year":"1965","unstructured":"Vladimir Iosifovich Levenshtein. 1965. Binary codes capable of correcting deletions, insertions and reversals. Doklady Akademii Nauk SSSR, 163, 4 (1965), 845\u2013848. http:\/\/mi.mathnet.ru\/eng\/dan31411","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90016-4"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2017.13"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2024.94"},{"key":"e_1_3_2_1_36_1","volume-title":"Threshold Approximate Matching in Grammar-Compressed Strings. In Prague Stringology Conference, PSC 2014","author":"Tiskin Alexander","year":"2014","unstructured":"Alexander Tiskin. 2014. Threshold Approximate Matching in Grammar-Compressed Strings. In Prague Stringology Conference, PSC 2014, Jan Holub and Jan \u017d\u010f\u00e1rek (Eds.). 124\u2013138. http:\/\/www.stringology.org\/event\/2014\/p12.html"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-023-10146-8"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649604","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:46Z","timestamp":1750178206000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":38,"alternative-id":["10.1145\/3618260.3649604","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649604","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}