Name
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(1/2-epsilon)) 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.STACS.2018.22 | Leibniz International Proceedings in Informatics |
Keywords | DocType | Volume |
Exact Pattern Matching with Wildcards,Hamming Distance,Inner Product,Conditional Lower Bounds | Journal | 96 |
ISSN | Citations | PageRank |
1868-8969 | 0 | 0.34 |
References | Authors | |
20 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Allan Grønlund Jørgensen | 2 | 145 | 7.31 |
| Kasper Green Larsen | 3 | 355 | 29.32 |
| Tatiana A. Starikovskaya | 4 | 71 | 14.95 |