2026-07-24T03:13:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16373 2024-03-06T10:57:18Z ddc:004 open_access

Improved Sublinear-Time Edit Distance for Preprocessed Strings Bringmann, Karl Cassis, Alejandro Fischer, Nick Nakos, Vasileios Edit Distance Property Testing Preprocessing Precision Sampling We study the problem of approximating the edit distance of two strings in sublinear time, in a setting where one or both string(s) are preprocessed, as initiated by Goldenberg, Rubinstein, Saha (STOC '20). Specifically, in the (k, K)-gap edit distance problem, the goal is to distinguish whether the edit distance of two strings is at most k or at least K. We obtain the following results: - After preprocessing one string in time n^{1+o(1)}, we can solve (k, k ⋅ n^o(1))-gap-gap edit distance in time (n/k + k) ⋅ n^o(1). - After preprocessing both strings separately in time n^{1+o(1)}, we can solve (k, k ⋅ n^o(1))-gap edit distance in time kn^o(1). Both results improve upon some previously best known result, with respect to either the gap or the query time or the preprocessing time. Our algorithms build on the framework by Andoni, Krauthgamer and Onak (FOCS '10) and the recent sublinear-time algorithm by Bringmann, Cassis, Fischer and Nakos (STOC '22). We replace many complicated parts in their algorithm by faster and simpler solutions which exploit the preprocessing. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karl Bringmann and Alejandro Cassis and Nick Fischer and Vasileios Nakos 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.32 urn:nbn:de:0030-drops-163734 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.32 eng https://creativecommons.org/licenses/by/4.0/legalcode