TY - GEN
T1 - Sketching, streaming, and fine-grained complexity of (weighted) LCs
AU - Bringmann, Karl
AU - Chaudhury, Bhaskar Ray
N1 - Publisher Copyright:
© Karl Bringmann and Bhaskar Ray Chaudhury.
PY - 2018/12
Y1 - 2018/12
N2 - 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(min{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.
AB - 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(min{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.
KW - Algorithms
KW - Communication complexity
KW - Run-length encoding
KW - SETH
UR - http://www.scopus.com/inward/record.url?scp=85079494792&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85079494792&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FSTTCS.2018.40
DO - 10.4230/LIPIcs.FSTTCS.2018.40
M3 - Conference contribution
AN - SCOPUS:85079494792
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
A2 - Ganguly, Sumit
A2 - Pandya, Paritosh
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
Y2 - 11 December 2018 through 13 December 2018
ER -