Petersburg Department of Steklov Institute of Mathematics Monday, 20 March 2006, 14:00 (note the unusual weekday)
Cybernetica Bldg (Akadeemia tee 21), room B101
Slides from the talk [pdf]
Abstract: There is a new topic in algorithm design: processing compressed objects without unpacking. For a number of problems, we now have a more efficient algorithms than just "unpack-and-solve". In the talk, I will survey the field and present a series of new algorithms.
The central result is an algorithm for fully compressed pattern matching. For given compressed strings P and T (Lempel-Ziv compression), we determine whether P is a substring in T. The algorithm works in cubic time from the COMPRESSED size of input. The previously known algorithm (1997) works in n^4. Then algorithms for finding periods, subsequences and covers will be presented. However, computing Hamming distance and longest common subsequence is NP-hard for compressed strings.
The talk will be concluded by a series of open problems in complexity theory and algorithms.