Designing Algorithms

Daily life is increasingly determined by algorithms, that are in their turn the building blocks of large software systems. It is therefore essential to design algorithms that are correct, transparent, efficient, and secure, and to incorporate them in high-quality systems.

The concept of algorithms is closely linked to research questions about computability and hence touches upon the ultimate limits of scientific knowledge. This immediately suggests deep and intriguing questions for our research. Under what conditions do hard optimization and prediction problems become efficiently solvable? Are there problems that will remain forever outside our computational reach (most famously, the /P versus NP/ problem)? Can we ingeniously turn this question around and use the computational complexity of algorithms to create encryption systems that are provably secure? And how can we design algorithms that take full advantage of the astonishing properties of quantum computers to perform multiple calculations simultaneously, resulting in dramatic speed-ups? While such questions are abstract, curiosity-driven and motivated by scientific excitement rather than day-to-day pressures, their potential long-term impact is huge.

Our scientific investigations also address problems related to the pressing demands for guaranteed quality in complex software systems. We therefore investigate formal tools and methods to define, measure, validate and optimize specific quality aspects. Examples include the design of special-purpose languages that simplify the expression of domain-specific actions while guaranteeing certain properties, database architectures that can efficiently manage intricate queries using large datasets, and mathematical proofs that formally show the correctness of software.