Ivan Mihajlin (University of California San Diego, USA)

Machine learning and fine-grained complexity

Programm / Abstract:
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.

am Mittwoch den 15. April 2020 um 16:30

MPI für Mathematik in den Naturwissenschaften Leipzig
Videobroadcast 3. Etage

eingetragen von Antje Vandenberg(Antje.Vandenberg@mis.mpg.de, 0341 9959 50)

zurück zum Kalender               Mathematics Calendar of the AMS