Upcoming IGAFIT Colloquia

The IGAFIT Algorithmic Colloquia are organized biweekly on Thursdays at 14:00 CEST. After the talk we will have an online networking/discussion session for approximately 1 hour. Both of these events will be run through the Airmeet platform.

Follow us also on twitter and facebook.

To subscribe to the ICAFIT Algorithmic Colloquium mailing list with announcements send an email to igafit-colloquium-request@mimuw.edu.pl with subject SUBSCRIBE.

The schedule of IGAFIT Algorithmic Colloquia: (see also our schedule of past Colloquia)


IGAFIT Algorithmic Colloquium #14
May 20, 2021 (4pm CEST)
Link: TBA
Title: Algorithms with Predictions: Simpler Analyses and Better Running Times
Sergei Vassilvitskii, Google Research New York
Abstract: How can machine learning help traditional algorithm design and analysis? One idea is to equip online algorithms with some noisy predictions about the future. Recent work has shown that such “learning-augmented algorithms” can effectively interpolate between offline methods where the full input is known and worst-case online algorithms, resulting in a competitive ratio parameterized by the quality of the predictions.
In this talk, we expand on this work and show that the learning-augmented lens is powerful in and of itself. We first look at the classical secretary problem, and prove that different variants of this age-old problem can be thought of simply as different advice that is available to the algorithm. This view allows us to develop a single analysis to give tight bounds on competitive ratio for many of these variations.
We then turn from competitive ratio to running time, and show how that here too predictions can be helpful. Specifically, we consider the min weight perfect matching problem and show what kind of predictions can be used to improve the running time, effectively formalizing the “warm-start” problem.
Based on joint work with Michael Dinitz, Paul Duetting, Sungjin Im, Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Renato Paes Leme

IGAFIT Algorithmic Colloquium #15
June 10, 2021
Link: TBA
Title:
Ronitt Rubinfeld, MIT
Abstract:

IGAFIT Algorithmic Colloquium #16
June 17, 2021
Link: TBA
Polyhedral Techniques in Combinatorial Optimization
Ola Svensson, EPFL
Abstract:

IGAFIT Algorithmic Colloquium #17
July 1, 2021 (4pm CEST)
Link: TBA
Title:
Virginia Vassilevska Williams, MIT
Abstract:

Past IGAFIT Colloquium talks.


Follow us also on twitter and facebook.

To subscribe to the ICAFIT Algorithmic Colloquium mailing list with announcements send an email to igafit-colloquium-request@mimuw.edu.pl with subject SUBSCRIBE.