Mission

Informatics: Accelerated progress in computing through new algorithms

While the acceleration of hardware has been a landmark of progress in computing technology in the past few decades, the computing enhancements that it provides is dwarfed by the increase in speed, performance, and robustness resulting from new algorithms. As a point in case, the status of hardware and algorithms in 1970 allowed to compute an optimal tour of a traveling salesman (a classical optimization problem and accepted benchmark for computing power) through 120 cities. Increasing the number of cities from n to n+1 leads to a multiplicative increase of the number of possible tours by a factor of n. Thus, relying only on the increase of hardware speed, with today’s technology, and the algorithms of 1970 we could find optimal tours among only 135 cities. It is the progress in algorithms that, today, enables us to find optimal tours between many thousand of cities. Relying only on progress in hardware this performance would not be achievable in hundreds of years.

The Max Planck Institute for Informatics is devoted to cutting-edge research in informatics with a focus on algorithms and their applications in a broad sense. Our research ranges from foundations (algorithms and complexity, programming logics) to a variety of application domains (computer graphics, geometric computation, constraint solving, program verification, databases and information systems, and computational biology/bioinformatics).

On the fundamental research side, this involves first-class research on new algorithms.
The algorithmic work for applications encompasses the integration of new algorithms into full-fledged systems and concrete application scenarios that are of high practical relevance. This involves the implementation of comprehensive software platforms and their experimental evaluation in application settings.
We provide a stimulating environment for junior researchers.

Our goal is to have impact through publications, software and people alike.

We regard informatics as a field that strives towards grounding the use of computational resources on thorough understanding of the underlying principles of computational methods. This involves reasoning mathematically and/or formally about the behavior of algorithms wherever possible. Consequently, much of our fundamental research is of a fairly rigorous mathematical character. Some of that research lies in established fields of theoretical computer science (algorithms and complexity, programming logics). Before a concrete application background, many computational problems are so complex that their in-depth formal treatment is not feasible. Therefore, in these cases, our analysis of the involved algorithms is more experimental, usually in the form of systematic validation based on carefully curated application data and specially developed statistical models and, last but not least, of real life systems use in the application field. In fact, many problems in complex application areas are fuzzily stated or ill-formed, at first, such that modeling, i.e., giving a rigorous definition of a problem is a major aspect of the research.

We test the value of our ideas by integrating new algorithms into systems and assessing their utility in realistic settings. This experience is useful in the short term in refining our designs and invaluable in the long term in advancing our knowledge. Most of the major advances in informatics and algorithms research have come through this combination of new theoretical insights and experimental validation.

We provide a stimulating environment for junior researchers that enables them to develop their own research programs and build up their own groups. The institute runs an active fellowship program on both the PhD and postdoc level and, since the establishment of the institute, a large number of researchers have spread out over other institutions, many of them taking tenured positions.

We are also strongly committed to communicating our results. Exposing and testing our ideas in the research and development communities leads to improved understanding. We actively seek publication of our results and findings in professional journals and conferences, and we use our internet pages to make our results widely available to the community. We seek users for our prototype systems among those with whom we have common interests, and we encourage collaboration with researchers from academia and industry alike. We encourage our junior researchers to build their own research programs and to spread out over other institutions.