Space-efficient data structures, computing over compressed data
Representing data with minimal storage requirements has a long tradition for communication, but in recent years it has gained importance for maximizing the size of data sets that can be kept in fast memory. Unlike for traditional compression, this requires algorithms that can run directly on the compressed representation to make use of the data. I develop such methods for various problems whose space requirements adapt to the data at hand.
Analysis of algorithms, algorithm science, adaptive algorithms
I work on the design of efficient algorithms and data structures, and their mathematical analysis. By determining exact constant factors and analyzing how their performance depends on characteristics of the input (adaptive analysis), I develop improvements for fundamental building blocks of computer science like sorting, selecting, and searching in dictionaries.
Lazy Finger Search Trees
March 2021 - March 2022