Beyond Worst-Case Analysis in Algorithms

Moderne teoretisk datavitenskap står overfor en grunnleggende utfordring: nåværende metoder klarer ikke å forklare effektiviteten til moderne maskinlæringsalgoritmer. For å forsone algoritmisk utilgjengelighet med maskinlæring vil vi utvikle nyskapende algoritmiske og kompleksitetsmetoder, med mål om å gjøre betydelige fremskritt både innen teoretisk datavitenskap og maskinlæring. I de første to årene av prosjektet initierte vi arbeid innen flere forskningsretninger: Utvikling av algoritmer for forklarbar klynging. Konstruksjon av kjerneenheter (kompakt tilnærming) for klynging i ulike metrikker. Nyskapende algoritmer for beregning av lange sykluser og stier i grafer. Algoritmer for robust matrise-tilnærming. Utvikling av nye tilnærminger til konstruksjon av grafdekomponeringer. Algoritmiske utvidelser av klassiske matematiske teoremer innen ekstremal grafteori. Disse forskningsretningene tar sikte på å håndtere nåværende begrensninger og utfordringer innen teoretisk datavitenskap, spesielt med tanke på å forklare effektiviteten til maskinlæringsalgoritmer. I det tredje året av prosjektet initierte vi studier av flere retninger innen algoritmisk forskning utover analyse av verste tilfelle. De nye områdene er: distribuert databehandling temporale grafer. To forskningsworkshops ble organisert i 2024 med internasjonale deltakere.

The field of theoretical computer science faces a fundamental challenge: the worst-case analysis, the established framework to estimate the computational complexity of problems, fails to explain the effectiveness of modern machine learning algorithms. To address this fundamental challenge, we will revise the foundations of computer science by moving beyond worst-case analysis. We will develop novel algorithmic and complexity methods and use these methods to reconcile the worst-case algorithmic intractability with machine learning. The successful completion of our program will yield progress in both areas of theoretical computer science and machine learning, and hence, in almost every area of science and technology.