Monday, March 22, 2021

[DMANET] IGAFIT Algorithmic Colloquium - 4pm(!) CET, March 25: Beyond Worst-Case Analysis by Tim Roughgarden

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

March 25, 2021, 16:00 CET (not the usual 14:00 time)
Tim Roughgarden, Columbia University
Title: Beyond Worst-Case Analysis
Abstract: One of the primary goals of the mathematical analysis of
algorithms is to provide guidance about which algorithm is the "best" for
solving a given computational problem. Worst-case analysis summarizes the
performance profile of an algorithm by its worst performance on any input
of a given size, implicitly advocating for the algorithm with the
best-possible worst-case performance. Strong worst-case guarantees are the
holy grail of algorithm design, providing an application-agnostic
certification of an algorithm's robustly good performance.
However, for many fundamental problems and performance measures, such
guarantees are impossible and a more nuanced analysis approach is called
for. Research in "beyond worst-case analysis" develops alternatives to
worst-case analysis, with applications ranging from clustering to linear
programming to neural network training. This talk will highlight a mix of
classic results, recent developments, and open questions in the area.

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
You can find more information about the talk on IGAFIT web page:

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:

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
* 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.