Reading Group Algorithms
Seminar
Basic Information
| Given by: | Kurt Mehlhorn and Ruben Becker |
|---|---|
| Time: | Wednesday, 4:15 PM |
| Room: | 024 in E1.4 (MPII-Building) |
| First Meeting: | October, 26 |
| 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. 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 semester, more precisely until March, 1st. 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.
News
- The reading group on Dec, 14 has to be canceled due to illness.
- Please note that on Dec, 14, the reading group will take place at 3:00 PM already due to the MPII christmas party that will take place at 4:00 PM. In case that there is also a room change, I will announce this here as well as in the email on Dec, 14.
Schedule
| Date | Speaker | Topic | Reference |
|---|---|---|---|
| Oct, 26 | Ruben | Introduction to the Reading Group | |
| Ruben | Accelerated Newton Iteration: Roots of Black Box Polynomials and Matrix Eigenvalues | [Oct26] | |
| Nov, 2 | Davis | LP can be a cure for Parameterized Problems | [Nov2] |
| Nov, 9 | Marco | Cutting corners cheaply or how to remove Steiner points | [Nov9] |
| Nov, 16 | Reut | An Improved Distributed Algorithm for Maximal Independent Set | [Nov16] |
| Nov, 23 | Pavel | Approximate Undirected Maximum Flows in O(m polylog(n)) Time | [Nov23] |
| Nov, 30 | Sebastian | Simple parallel and distributed algorithms for spectral graph sparsification | [Nov30] |
| Dec, 7 | Daniel | Firefighting on Trees Beyond Integrality Gaps | [Dec7] |
| Dec, 14 | canceled | ||
| Jan, 11 | Aruni | Computing the Gromov-Hausdorff Distance for Metric Trees | [Jan11] |
| Jan, 18 | Philip | Bipartite Perfect Matching is in quasi-NC | [Jan18] |
| Jan, 25 | Julian | A Randomized Concurrent Algorithm for Disjoint Set Union | [Jan25] |
| Feb, 1 | Moritz | Approximating the minimum quadratic assignment problems | [Feb1] |
| Feb, 8 | Bhaskar | A Strengthening of a Theorem of Tutte on Hamiltonicity of Polyhedra | [Feb8] |
| Feb, 15 | Nabil | Almost tight bounds for eliminating depth cycles in three dimensions | [Feb15] |
Papers
This list is complete.