IGAFIT Algorithmic Colloquium is a online seminar series organized by IGAFIT. The event aims to provide a forum for research exchange and scientific interaction, to integrate the European algorithmic community, and to keep the community connected during the times of the pandemic. The goal is to present the highlights of algorithmic research and the most exciting works in this area. Nikhil Bansal (CWI, N&O group) is member of the organizing committee.
The upcoming seminar features Tim Roughgarden (Columbia University). Title of his lecture: 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.
To subscribe to the ICAFIT Algorithmic Colloquium mailing list with announcements send an email to igafit-colloquium-request@mimuw.edu.pl with subject SUBSCRIBE.
