The project concerns fundamental research in ICT, in particular within the fields of algorithms and complexity. The field of theoretical computer science is faced with a fundamental challenge: the predictions made by the theory do not match empirical observations. The objective of the proposed research is to address this fundamental problem by revising the foundations of theoretical computer science, changing how computational efficiency is measured in terms of the properties of the input data. In particular, we will establish multivariate algorithms as the standard approach to algorithm design and analysis. To reach the goals of this interdisciplinary research project, we will exploit cross-domain synergies and collaborate with the world leading scientists. Since computation permeates everything, the successful completion of our program will yield progress in all areas of science and technology, as well as in our daily lives.
Project leader: Fedor Fomin
Institution: Institutt for informatikk