Efficiently approximating edit distance between pseudorandom strings

DOI10.1137/1.9781611975482.71MaRDI QIDQ5236255zbMATH OpenOpenAlexFDO

Authors William Kuszmaul

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.04300

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Abstract: We present an algorithm for approximating the edit distance $operatornameed(x,y)$ between two strings $x$ and $y$ in time parameterized by the degree to which one of the strings $x$ satisfies a natural pseudorandomness property. The pseudorandomness model is asymmetric in that no requirements are placed on the second string $y$, which may be constructed by an adversary with full knowledge of $x$. We say that $x$ is emph{$(p,B)$-pseudorandom} if all pairs $a$ and $b$ of disjoint $B$-letter substrings of $x$ satisfy $operatornameed(a,b)gepB$. Given parameters $p$ and $B$, our algorithm computes the edit distance between a $(p,B)$-pseudorandom string $x$ and an arbitrary string $y$ within a factor of $O(1/p)$ in time $ildeO(nB)$, with high probability. Our algorithm is robust in the sense that it can handle a small portion of $x$ being adversarial (i.e., not satisfying the pseudorandomness property). In this case, the algorithm incurs an additive approximation error proportional to the fraction of $x$ which behaves maliciously. The asymmetry of our pseudorandomness model has particular appeal for the case where $x$ is a emph{source string}, meaning that $operatornameed(x,y)$ will be computed for many strings $y$. Suppose that one wishes to achieve an $O(alpha)$-approximation for each $operatornameed(x,y)$ computation, and that $B$ is the smallest block-size for which the string $x$ is $(1/alpha,B)$-pseudorandom. We show that without knowing $B$ beforehand, $x$ may be preprocessed in time $ildeO(n^{1.5}sqrtB)$, so that all future computations of the form $operatornameed(x,y)$ may be $O(alpha)$-approximated in time $ildeO(nB)$. Furthermore, for the special case where only a single $operatornameed(x,y)$ computation will be performed, we show how to achieve an $O(alpha)$-approximation in time $ildeO(n^{4/3}{B}^{2/3})$.

Recommendations

• Approximating edit distance in near-linear time
• Approximating edit distance in near-linear time
• A sublinear algorithm for weakly approximating edit distance
• The Smoothed Complexity of Edit Distance
• The smoothed complexity of edit distance

Cited in

(10)

• Computation of edit probabilities and edit distances for the A5-type keystream generator
• Period recovery of strings over the Hamming and edit distances
• Train tracks with gaps: applying the probabilistic method to trains
• The smoothed complexity of edit distance
• The Smoothed Complexity of Edit Distance
• A sublinear algorithm for weakly approximating edit distance
• A Probabilistic Analysis of a String Editing Problem and its Variations
• Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
• Near-linear time edit distance for indel channels
• Edit distance in near-linear time: it's a constant factor

This page was built for publication: Efficiently approximating edit distance between pseudorandom strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236255)