Ivan Mihajlin (University of California San Diego, USA)
Wednesday, April 15, 2020 - 16:30
MPI für Mathematik in den Naturwissenschaften Leipzig
 ,    , Videobroadcast, 3. Etage
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.

One day before the seminar, an announcement with the Zoom link will be sent to those who registered with Ivan Yamshchikov. For this please contact him at Ivan Yamshchikov.

submitted by Antje Vandenberg (Antje.Vandenberg@mis.mpg.de, 0341 9959 50)