Back to search

FRINATEK-Fri prosj.st. mat.,naturv.,tek

Beyond Worst-Case Analysis in Algorithms

Alternative title: Beyond Worst-Case Analysis in Algorithms

Awarded: NOK 12.0 mill.

Modern theoretical computer science faces a fundamental challenge: current methods fail to explain the effectiveness of modern machine learning algorithms. To reconcile algorithmic intractability with machine learning, we will develop novel algorithmic and complexity methods, aiming to progress significantly in both theoretical computer science and machine learning. In the first two years of the project, we initiated work in several research directions, including: - Developing algorithms for Explainable Clustering. - Constructions of coresets (compact approximation) for clusterings in various metrics. - Novel algorithms for computing long cycles and paths in graphs. - Algorithms for robust matrix approximation. - Development of new approaches to constructing graph decompositions. - Algorithmic extensions of the classic mathematical theorems of extremal graph theory. These research directions address current limitations and challenges in theoretical computer science, particularly in explaining the efficiency of machine learning algorithms.

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.

Funding scheme:

FRINATEK-Fri prosj.st. mat.,naturv.,tek