Algorithms with Predictions
Seminar
Basic Information
| Given by: | Kurt Mehlhorn, Nidhi Rathi, Golnoosh Shahkarami |
|---|---|
| Time: | Tuesdays, 2-4pm |
| Room: | 024 (E1 4) |
| First Meeting: | October 22, 2024 |
| Credits: | 7 credit points |
| Prerequisites: | This is a theoretical seminar that will require mathematical maturity (in particular, the ability to understand and write formal mathematical proofs) and a good background in algorithms. A proper preparation of your talk will require non-trivial effort. The target audience of this seminar are master students, PhD students, as well as postdocs. |
| Deadlines: | TBA |
Description
Learning-augmented algorithms is a recent line of research that seeks to blend the strengths of machine learning with classical algorithms, aiming for both practical efficiency and robustness. In this framework, we are provided with predictions about missing data—such as future data in online algorithms or private data in truthful mechanisms—though the accuracy of these predictions is uncertain. The objective is to improve the performance guarantees when predictions are accurate and to incur only a constant loss when predictions are poor.
The instructors will begin with introductory lectures covering foundational concepts to help students choose their paper or topic for the seminar. Additionally, we have invited three experts in the field to give guest lectures. The seminar is open to all interested students and postdocs. To earn credit points, students must meet the following requirements:
Choose a paper and:
- give a regular presentation
- write a short summary
- put a comment at www.alphaxiv.org
The presentation must be discussed with us at least one week before your scheduled talk. Feel free to reach out to us (nrathi@mpi-inf.mpg.de, gshahkar@mpi-inf.mpg.de) with any questions!
Schedule
| Date | Speaker |
|---|---|
| October 22 | Golnoosh Shahkarami |
| October 29 | Nidhi Rathi |
| November 5 | Invited Speaker: Nicole Megow |
| November 12 | Invited Speaker: Vasilis Gkatzelis |
| November 19 | Invited Speaker: Antonios Antoniadis |
| Papers | Authors |
|---|---|
| A Universal Error Measure for Input Predictions Applied to Online Graph Problems | Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie, Michelle Sweering |
| Online metric algorithms with untrusted predictions | Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, Bertrand Simon |
| Online Graph Algorithms with Predictions | Yossi Azar, Debmalya Panigrahi, Noam Touitou |
| Secretary and Online Matching Problems with Machine Learned Advice | Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, Pavel Kolev |
| A Novel Prediction Setup for Online Speed-Scaling | Antonios Antoniadis, Peyman Jabbarzade Ganje, Golnoosh Shahkarami |
| Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location | Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, Xizhi Tan |
| Mechanism Design with Predictions | Chenyang Xu, Pinyan Lu |
| Strategyproof Scheduling with Predictions | Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan |
| Learning-Augmented Metric Distortion via (p,q)-Veto Core | Ben Berger, Michal Feldman, Vasilis Gkatzelis, Xizhi Tan |
| Incremental Topological Ordering and Cycle Detection with Predictions | Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Shikha Singh |
| Learning Augmented Binary Search Trees | Honghao Lin, Tian Luo, David P. Woodruff |
How to apply?
Application for seminars is possible through the central SIC seminar system (https://seminars.cs.uni-saarland.de/seminars2425).
If you are interested in attending specifically this seminar, we kindly recommend you to
- send a request by e-mail to Nidhi Rathi or Golnoosh Shahkarami. Please indicate your full name and enrollment number.
- apply for this seminar in the central SIC seminar system.