Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS

Karl Bringmann, Bhaskar Ray Chaudhury

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…