Multivariate Algorithms: New domains and paradigms

Formålet med prosjektet er å drive grunnforskning i informatikk og informasjonsteknologi, spesifikt innen algoritmer og kompleksitet. Teoretisk informatikk står ovenfor en grunnleggende utfordring: effektivitets-estimater utledet ved hjelp av teoretiske modeller sammenfaller dårlig med faktiske empiriske observasjoner. I dette prosjektet skal vi angripe dette problemet ved å endre selve grunnmuren i teoretisk informatikk - modellen for hvordan beregningseffektivitet blir målt som en funksjon av input-dataen. Mer spesifikt vil vi etablere fler-variabel algoritmisk analyse som den nye standarden for å måle algoritmisk effekivitet og drivkraften bak algoritmedesign. For å nå de ambisiøse målene i dette forskningsprosjektet vil vi utnytte synergier som oppstår i krysningen mellom informatikk og nærliggende felt, samt samarbeide med verdensledende forskere i de relevante feltene. Siden beregning gjennomsyrer alt, vil en gjennomføring av dette forskningsprogrammet både gi fremskritt innen alle vitenskapsområder og påvirke vårt daglige liv. I 2018 og 2019 vi utvikle metoder og teknikker for multivariabel algoritmisk analyse. Vi lykkes med å oppnå nye algoritmiske og kompleksitetsresultater for beregningsproblemer fra flere felt. Alle disse resultatene er presentert på internasjonale konferanser og publisert i prestisjetunge internasjonale tidsskrifter, samt i Open access register for elektroniske preprints ArXiv. I 2020 utvidet vi den multivariate tilnærmingen til domenene til AI og maskinlæring uten tilsyn.

The highlights of the results obtained within the project are: (a) New tools for designing efficient approximation schemes in planar and geometric graphs (b) Meta-theorems about efficient preprocessing (c) Lower bounds on the solvability of Integer Linear Programming (d) Developing multivariate algorithmic analysis for clustering problems (e) Novel multivariate algorithmic approach to the robustness of Principal Component Analysis.

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.