[DMANET] IGAFIT Algorithmic Colloquium - 4pm(!) CEST, May 20:Algorithms with Predictions: Simpler Analyses and Better Running Times by Sergei Vassilvitskii

Dear all,
Please note the unusual time(!) for the next talk on the IGAFIT
Algorithmic Colloquium this Thursday:

May 20, 2021, 16:00 CEST (not the usual 14:00 time)
Sergei Vassilvitskii, Google Research New York
Title: Algorithms with Predictions: Simpler Analyses and Better Running
Times
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

We would like to invite you to take part in the event including the
networking session. This new event aims to integrate the European
algorithmic community and keep it connected during the times of the
pandemic. The meeting will be held using the Airmeet platform and to attend
please go to https://www.airmeet.com/e/ca918750-b74a-11eb-be0c-eb03b5e29431.
You can find more information about the talk on IGAFIT web page:
http://igafit.mimuw.edu.pl/?page_id=483786.

In order to access the Airmeet platform, you will need to register, so that
others know who you are. Then before and after the talk, you will be
located inside a Social Lounge, where discussion tables are visible. Most
of the tables can have up to 8 chairs, and you can join a table by clicking
the "Take a Seat" button on a table. This way you will be able to talk to
people seated currently at the table. When the session starts you will be
automatically switched to see the stage. You can find more instructions on
how to use Airmeet here:
https://www.airmeet.com/hub/step-by-step-guide-use-airmeet-for-attendees/.

We invite you to take part in the event. Please advertise broadly and bring
your students/postdocs as well.

Organization Committee:
Nikhil Bansal
Artur Czumaj
Andreas Feldmann
Danupon Nanongkai
Adi Rosen
Eva Rotenberg
Piotr Sankowski
Christian Sohler

**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************