Browse/search for people

Publication - Dr Raphael Clifford

    Upper and lower bounds for dynamic data structures on strings

    Citation

    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. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

    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.

    Full details in the University publications repository