Machine learning and fine-grained complexity

  • Ivan Mihajlin (University of California San Diego, USA)
Live Stream


In traditional computational complexity, there is a convention that if a problem has a polynomial time algorithm it is already a simple problem. Obviously, in practice there is a huge difference between an algorithm with running time n^2 and one with running time n^100. This observation gave rise to a more modern approach: fine-grained complexity. The goal of it is to pinpoint the hardness of a problem as precisely as possible.
In this talk, we will cover some basic techniques used in fine-grained complexity and the limitations of these techniques. Then we will show that under widely believed assumptions we already have optimal algorithms for some of the cornerstone problems in Machine learning.

01.04.20 21.01.21

Machine Learning Online Seminar

MPI for Mathematics in the Sciences Live Stream

Katharina Matschke

MPI for Mathematics in the Sciences Contact via Mail