Sketching, streaming, and fine-grained complexity of (weighted) LCs

Karl Bringmann, Bhaskar Ray Chaudhury

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
EditorsSumit Ganguly, Paritosh Pandya
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770934
DOIs
StatePublished - Dec 2018
Externally publishedYes
Event38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018 - Ahmedabad, India
Duration: Dec 11 2018Dec 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume122
ISSN (Print)1868-8969

Conference

Conference38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
Country/TerritoryIndia
CityAhmedabad
Period12/11/1812/13/18

Keywords

  • Algorithms
  • Communication complexity
  • Run-length encoding
  • SETH

ASJC Scopus subject areas

  • Software

Cite this