Henzinger_Monika Group

Algorithms

To save resources in computing the goal is usually to minimize computing time and storage space. The research field of efficient algorithms and data structures wants to understand how to save these resources, both by designing better algorithms and by proving bounds on the limits of possible savings. One particular area of focus in our research on efficient algorithms are dynamic settings where the input to the program is updated repeatedly and after each update the new solution needs to be found much faster than restarting the computation on the new input.

A second area of our research is designing algorithms that protect the privacy of the input data. This can be achieved by adding suitable noise to the input and the goal of the research is to minimize the amount of noise as it reduces the information that can be gained from the output and can also slow down the algorithm. The amount of noise depends on what information needs to be computed from the data and what kind of privacy guarantees are desired. Again, our focus is on the dynamic setting where the input data changes continuously.

A third area of our research is to turn the theoretically best algorithms into simple, practical algorithms that we implement and evaluate empirically. As before we are especially interested in algorithms for dynamically changing inputs.