2018/10/02 by Karl Bringmann, Bringmann, Karl, Bhaskar Ray Chaudhury +1 · 2 citations
Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Computer Science #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #cs.DS
paper · pdf · doi:10.48550/arxiv.1810.01238
To appear in FSTTCS 2018
arxiv created 2018/10/02 · openalex publication_date 2018/10/02 · arxiv updated 2018/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study sketching and streaming algorithms for the Longest Common Subsequence problem (LCS) on strings of small alphabet size |Σ|. 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 O(L|Σ| - 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 O(\textrmmin\nm, n + m| Σ|\)-time algorithm for this problem, on strings x,y of length n,m, with n ≥ m. We prove optimality of this running time up to lower order factors, assuming the Strong Exponential Time Hypothesis.