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.