Upper and lower bounds for dynamic data structures on strings

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

doi:10.4230/LIPIcs.STACS.2018.22

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 proceeding › Conference Contribution (Conference Proceeding)

12 Citations (Scopus)

106 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(m¹/^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 language	English
Title of host publication	35th Symposium on Theoretical Aspects of Computer Science, STACS 2018
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages	14
ISBN (Electronic)	9783959770620
DOIs	https://doi.org/10.4230/LIPIcs.STACS.2018.22
Publication status	Published - 28 Feb 2018
Event	35th Symposium on Theoretical Aspects of Computer Science, STACS 2018 - Caen, France Duration: 28 Feb 2018 → 3 Mar 2018

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Volume	96
ISSN (Print)	1868-8969

Conference

Conference	35th Symposium on Theoretical Aspects of Computer Science, STACS 2018
Country/Territory	France
City	Caen
Period	28/02/18 → 3/03/18

Keywords

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

Access to Document

10.4230/LIPIcs.STACS.2018.22Licence: Unspecified

Full-text PDF (final published version)
This is the final published version of the article (version of record). It first appeared online via DROPS at http://drops.dagstuhl.de/opus/volltexte/2018/8508/ . Please refer to any applicable terms of use of the publisher.
Final published version, 538 KBLicence: CC BY

Handle.net

Persistent link

Cite this

Clifford, R., Grønlund, A., Larsen, K. G., & Starikovskaya, T. (2018). Upper and lower bounds for dynamic data structures on strings. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018 Article 22 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 96). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2018.22

@inproceedings{85eba008660b454f865879cc4a91ba91,

title = "Upper and lower bounds for dynamic data structures on strings",

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.",

keywords = "Conditional Lower Bounds, Exact Pattern Matching with Wildcards, Hamming Distance, Inner Product",

author = "Raphael Clifford and Allan Gr{\o}nlund and Larsen, {Kasper Green} and Tatiana Starikovskaya",

year = "2018",

month = feb,

day = "28",

doi = "10.4230/LIPIcs.STACS.2018.22",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

booktitle = "35th Symposium on Theoretical Aspects of Computer Science, STACS 2018",

note = "35th Symposium on Theoretical Aspects of Computer Science, STACS 2018 ; Conference date: 28-02-2018 Through 03-03-2018",

}

Clifford, R, Grønlund, A, Larsen, KG & Starikovskaya, T 2018, Upper and lower bounds for dynamic data structures on strings. in 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018., 22, Leibniz International Proceedings in Informatics (LIPIcs), vol. 96, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, Caen, France, 28/02/18. https://doi.org/10.4230/LIPIcs.STACS.2018.22

Upper and lower bounds for dynamic data structures on strings. / Clifford, Raphael; Grønlund, Allan; Larsen, Kasper Green et al.
35th Symposium on Theoretical Aspects of Computer Science, STACS 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. 22 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 96).

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

TY - GEN

T1 - Upper and lower bounds for dynamic data structures on strings

AU - Clifford, Raphael

AU - Grønlund, Allan

AU - Larsen, Kasper Green

AU - Starikovskaya, Tatiana

PY - 2018/2/28

Y1 - 2018/2/28

N2 - 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.

AB - 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.

KW - Conditional Lower Bounds

KW - Exact Pattern Matching with Wildcards

KW - Hamming Distance

KW - Inner Product

UR - http://www.scopus.com/inward/record.url?scp=85044523565&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.STACS.2018.22

DO - 10.4230/LIPIcs.STACS.2018.22

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:85044523565

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018

Y2 - 28 February 2018 through 3 March 2018

ER -

Clifford R, Grønlund A, Larsen KG, Starikovskaya T. Upper and lower bounds for dynamic data structures on strings. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2018. 22. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.STACS.2018.22

Upper and lower bounds for dynamic data structures on strings

Abstract

Publication series

Conference

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this