Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Streaming Algorithms For Computing Edit Distance Without Exploiting
  Suffix Trees   The edit distance is a way of quantifying how similar two strings are to one
another by counting the minimum number of character insertions, deletions, and
substitutions required to transform one string into the other.
  In this paper we study the computational problem of computing the edit
distance between a pair of strings where their distance is bounded by a
parameter $k\ll n$. We present two streaming algorithms for computing edit
distance: One runs in time $O(n+k^2)$ and the other $n+O(k^3)$. By writing
$n+O(k^3)$ we want to emphasize that the number of operations per an input
symbol is a small constant. In particular, the running time does not depend on
the alphabet size, and the algorithm should be easy to implement.
  Previously a streaming algorithm with running time $O(n+k^4)$ was given in
the paper by the current authors (STOC'16). The best off-line algorithm runs in
time $O(n+k^2)$ (Landau et al., 1998) which is known to be optimal under the
Strong Exponential Time Hypothesis.

25
The categories of this paper are: patt-sol
17
The categories of this paper are: q-fin
8
The categories of this paper are: hep-ex
37
The categories of this paper are: supr-con
35
The categories of this paper are: mtrl-th
24
The categories of this paper are: dg-ga
9
The categories of this paper are: nlin
16
The categories of this paper are: stat
2
The categories of this paper are: math
0
The categories of this paper are: hep-ph
36
The categories of this paper are: cmp-lg
3
The categories of this paper are: physics
6
The categories of this paper are: astro-ph
34
The categories of this paper are: chem-ph
18
The categories of this paper are: econ
19
The categories of this paper are: eess