Reading Group Algorithms
Seminar
Basic Information
| Given by: | Kurt Mehlhorn, Marvin Künnemann and Ruben Becker |
|---|---|
| Time: | Wednesday, 4:15 PM |
| Room: | 024 in E1.4 (MPII-Building), except for Nov, 4: 0.10 in E1.7 MMCI-Building |
| First Meeting: | October, 21 |
| Credits: | 7 credit points |
| Prerequisites: | You should bring a solid background in algorithms and data structures. This is an advanced seminar. The papers are challenging and a proper preparation of your talk will require some effort. Thus, you should bring a great passion for theoretical computer science. The target audience of this reading group are master students, PhD students, as well as postdocs. |
Description
We will read (more or less) recent papers in theoretical computer science. The paper may be less recent if there is interesting follow-up work. In each session we have a regular presentation (40-60 minutes + discussion) of one paper. Sometimes this is preceded by a short presentation of another paper (up to 20 minutes). The reading group is open for all interested students and postdocs. Students aiming to get credits give a regular talk and write a short summary about the paper.
You earn the usual 7 credit points for a seminar if you (i) give a regular presentation of the paper given to you, and (ii) write a short summary (about 5 pages). The summary should be handed in within the first two weeks after the end of the lecture period. You will receive comments and can improve your summary based on our comments. The presentation needs to be discussed with us at least one week before your scheduled talk in the reading group (you are supposed to give a practice talk to your supervisor).
The reading group counts as a seminar in your study program. You can register by sending an e-mail to Ruben. Please make sure that you read the section on prerequisites above before you register.
Schedule
| Date | Speaker | Topic | Reference |
|---|---|---|---|
| Oct, 21 | Marvin and Ruben | Introduction to the Reading Group | |
| Ruben Becker | A Polynomial Time Algorithm for Diophantine Equations in One Variable | [Oct21] | |
| Oct, 28 | Marvin Künnemann | Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility | [Oct28] |
| Nov, 4 | Pavel Kolev | Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates | [Nov4] |
| Nov, 11 | Davis Isaac | Relations between average case complexity and approximation complexity | [Nov11] |
| Nov, 18 | Daniel Vaz | Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem | [Nov18] |
| Nov, 25 | Erik Jan van Leeuwen | Designing FPT algorithms for cut problems using randomized contractions | [Nov25] |
| Dec, 2 | Jugal Garg | A strongly polynomial algorithm for generalized flow maximization | [Dec2] |
| Dec, 9 | Parinya Chalermsook | Tight hardness of approximating set cover | [Dec9] |
| Dec, 16 | Martin Geibel | Minimum Cost Flows in Graphs with Unit Capacities | [Dec16] |
| Jan, 6 | cancelled | ||
| Jan, 13 | Thomas Kesselheim | Understanding the Price of Anarchy of Non-Truthful Mechanisms | [Jan13] |
| Jan, 20 | Karl Bringmann | Valiant's Parser (and why it's probably optimal) | [Jan20] |
| Jan, 27 | David Ziegler | Sparsified Cholesky Solvers for SDD linear systems | [Jan27] |
| Feb, 3 | Hang Zhou | Dynamic Graph Connectivity in Polylogarithmic Worst Case Time | [Feb3] |
| Feb, 10 | Antonios Antoniadis | On the optimality of approximation schemes for the classical scheduling problem | [Feb10] |
| Mar, 2 | Kurt Mehlhorn | Hollow Heaps | [Mar2] |
Papers
This list is complete.