On 21.01.2016 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Tomasz Kociumaka. He will give a talk on his recent result on “Optimal Dynamic Strings”. The abstract is given below.

We plan to have a group discussion and joint lunch after his talk.

Abstract:

We study the fundamental problem of maintaining a dynamic collection

of strings under the following operations: concatenate two strings,

split a string into two at a given position, determine the

lexicographical order (smaller, equal, greater) between two strings,

calculate the longest common prefix of two strings. We present a data

structure for this problem, in which updates require only O(log n)

worst-case time with high probability, with n being the total length

of all strings in the collection, and queries take constant worst-case

time. On the lower bound side, we prove that even if the only possible

query is checking equality of two strings, either updates or queries

must take amortized Ω(log n) time; hence our implementation is

optimal. Our data structure can be used as a basic building block to

solve other string problems, such as pattern matching in dynamic

string collections, pattern matching in a history is an edited text,

and processing grammar-compressed strings.

Joint work with Paweł Gawrychowski, Jakub Łącki, Adam Karczmarz, and Piotr Sankowski