Upper and lower bounds for dynamic data structures on strings

Raphael Clifford, Allan Grønlund, Kasper Green Larsen, Tatiana Starikovskaya

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

3 Citations (Scopus)
48 Downloads (Pure)

Abstract

We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the pattern of length m and a substring of a longer text. We give both conditional and unconditional lower bounds for variants of exact matching with wildcards, inner product, and Hamming distance computation via a sequence of reductions. As an example, we show that there does not exist an O(m1/2-e) time algorithm for a large range of these problems unless the online Boolean matrix-vector multiplication conjecture is false. We also provide nearly matching upper bounds for most of the problems we consider.

Original languageEnglish
Title of host publication35th Symposium on Theoretical Aspects of Computer Science, STACS 2018
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages14
ISBN (Electronic)9783959770620
DOIs
Publication statusPublished - 28 Feb 2018
Event35th Symposium on Theoretical Aspects of Computer Science, STACS 2018 - Caen, France
Duration: 28 Feb 20183 Mar 2018

Publication series

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

Conference

Conference35th Symposium on Theoretical Aspects of Computer Science, STACS 2018
CountryFrance
CityCaen
Period28/02/183/03/18

Keywords

  • Conditional Lower Bounds
  • Exact Pattern Matching with Wildcards
  • Hamming Distance
  • Inner Product

Fingerprint Dive into the research topics of 'Upper and lower bounds for dynamic data structures on strings'. Together they form a unique fingerprint.

Cite this