Name
Abstract | ||
|---|---|---|
study sketching and streaming algorithms for the Longest Common Subsequence problem (LCS) on strings of small alphabet size $|Sigma|$. For the problem of deciding whether the LCS of strings $x,y$ has length at least $L$, we obtain a sketch size and streaming space usage of $mathcal{O}(L^{|Sigma| - 1} log L)$. We also prove matching unconditional lower bounds. As an application, we study a variant of LCS where each alphabet symbol is equipped with a weight that is given as input, and the task is to compute a common subsequence of maximum total weight. Using our sketching algorithm, we obtain an $mathcal{O}(textrm{min}{nm, n + m^{{lvert Sigma rvert}}})$-time algorithm for this problem, on strings $x,y$ of length $n,m$, with $n ge m$. prove optimality of this running time up to lower order factors, assuming the Strong Exponential Time Hypothesis. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.FSTTCS.2018.40 | FSTTCS |
DocType | Volume | Citations |
Conference | abs/1810.01238 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Karl Bringmann | 1 | 427 | 30.13 |
| Bhaskar Ray Chaudhury | 2 | 0 | 4.39 |