@online{Bringmann_arXiv1810.01238,
TITLE = {Sketching, Streaming, and Fine-Grained Complexity of (Weighted) {LCS}},
AUTHOR = {Bringmann, Karl and Ray Chaudhury, Bhaskar},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1810.01238},
EPRINT = {1810.01238},
EPRINTTYPE = {arXiv},
YEAR = {2018},
ABSTRACT = {We 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$. We prove optimality of this running time up to lower order factors, assuming the Strong Exponential Time Hypothesis.},
}