On 10.12.2015 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Paweł Gawrychowski. He will give a talk on his recent result on “Approximating LZ77 via Small-Space Multiple-Pattern Matching”. The abstract is given below.

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

Abstract:

We generalize the well-known Karp-Rabin string matching to handle

multiple patterns in O(nlogn+m) time and O(s) space, where n is the

length of the text and m is the total length of the s patterns,

returning correct answers with high probability. As a prime

application of our algorithm, we show how to approximate the LZ77

parse of a string of length n. If the optimal parse consists of z

phrases, using only O(z) working space we can return a parse

consisting of at most (1+ε)z phrases in O(1/ε n logn) time, for any

ε∈(0,1].

Joint work with Johannes Fischer, Travis Gagie, and Tomasz Kociumaka.