Teaching

Reading Group Algorithms (B), Winter 2012/13

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.

News:

Schedule:

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