max planck institut
mpii logo Minerva of the Max Planck Society


Reading Group Algorithms (B), Winter 2012/13

Kurt Mehlhorn and Karl Bringmann

Time: Thursday, 12:30 to 14:00
First meeting: First Wednesday of the winter 2012/13 term, i.e., October 17.
Room: 024 on the ground floor of the MPI building (E1.4), except on Nov 08 and Nov 22, where we are in room 001 of the MMCI building (E1.7)
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.
Content: 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 the first 45 minutes, we will have short presentations of one or two different papers. In the second 45 minutes, we have a regular presentation (40 minutes + 5 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.
Credits: 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 four weeks after the end of the semester. The presentation needs to be discussed with us at least one week before your scheduled talk in the reading group.
Date Speaker Topic Reference
Oct 17 Kurt and Karl Introduction to the reading group
Karl Changing base without losing space [Oct17]
Oct 25 Anna Adamaszek A Polylogarithmic-Competitive Algorithm for the k-Server Problem [Oct25]
Nov 1 Public Holiday (Allerheiligen/All Saints' Day)
Nov 8
room change!
Tobias Mömke Approximating Graphic TSP by Matchings [Nov8]
Nov 15 Pawel Gawrychowski Orthogonal range searching on the RAM, revisited [Nov15]
Nov 22
room change!
Kurt Computing Equilibrium Prices for the Arrow-Debreu Market Model [Nov22]
Nov 29 Magnus Wahlström Faster algorithms for Hamiltonian Cycle [Nov29]
Dec 6 Ruben Becker Map Graphs [Dec06]
Dec 13 Pavel Kolev Multi-way spectral partitioning and higher-order Cheeger inequalities [Dec13]
Dec 20 Martin Hoefer Learning Algorithms for Interference Problems [Dec20]
Jan 10 Petro Lutsyk Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations [Jan10]
Jan 17 Christos Orlis Finding odd cycle transversals [Jan17]
Jan 24 Matthias Mnich Computing Correlated Equilibria in Multiplayer Games [Jan24]
Jan 31 Bach-Thi Dinh Color-Coding [Jan31]
Feb 7 Thomas Sauerwald Balls into Bins Via Local Search [Feb07]
References: [Oct17] "Changing base without losing space" by Y. Dodis, M. Patrascu, and M. Thorup.
[Oct25] "A Polylogarithmic-Competitive Algorithm for the k-Server Problem" by N. Bansal, N. Buchbinder, A. Madry, and S. Naor.
[Nov8] "Approximating Graphic TSP by Matchings" by Tobias Mömke and Ola Svensson.
[Nov15] "Orthogonal range searching on the RAM, revisited" by Timothy M. Chan, Kasper Green Larsen, and Mihai Patrascu.
[Nov22] "A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market" by Ran Duan and Kurt Mehlhorn.
[Nov29] "Determinant Sums for Undirected Hamiltonicity" by Andreas Björklund.
[Dec06] [Jens M. Schmidt] "Map graphs" by Zhi-Zhong Chen, Michelangelo Grigni, and Christos H. Papadimitriou.
[Dec13] [He Sun] "Multi-way spectral partitioning and higher-order Cheeger inequalities" by James R. Lee, Shayan Oveis Gharan, and Luca Trevisan.
[Dec20] "Convergence Time of Power Control Dynamics" by J. Dams, M. Hoefer, and T. Kesselheim. and "On a game theoretic approach to capacity maximization in wireless networks" by E. Asgeirsson and P. Mitra.
[Jan10] [Kurt Mehlhorn] "Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations" by Kousha Etessami, Alistair Stewart, and Mihalis Yannakakis.
[Jan17] [Geevarghese Philip] "Finding odd cycle transversals" by Bruce A. Reed, Kaleigh Smith, and Adrian Vetta.
[Jan24] "Computing Correlated Equilibria in Multiplayer Games" by Christos Papadimitriou and Tim Roughgarden.
[Jan31] [Geevarghese Philip] "Color-coding" by Noga Alon, Raphael Yuster, and Uri Zwick.
[Feb07] "Balls into Bins Via Local Search" by Paul Bogdan, Thomas Sauerwald, Alexandre Stauffer, and He Sun.
Papers: Below is a list of papers which are available for presentation in the reading group. If you are interested in presenting a paper that is not from this list, please let us know well in advance so we can check appropriateness. If you are interested in presenting one of the papers below, please notify Karl. The names in brackets indicate who suggested the respective paper. In most cases, he/she will be the supervisor of your presentation. However, please check with us first as your talk might also be supervised by a different person.
This list is complete.

More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)