Algorithms & Complexity

String Algorithms and Data Compression

Strings (texts, sequences) appear everywhere in our daily lives, and they constitute some of the biggest datasets generated by humanity (such as the petabytes of genomic data). We develop cutting-edge algorithms for processing huge strings of all kinds, focusing on classical problems such as measuring the similarity of two strings or finding all fragments of a long text that closely resemble a given pattern. We design our algorithms for multiple modern models of computation capable of handling big data. In particular, we develop compression schemes efficiently supporting basic computational tasks on the repetitive sequences.