max planck institut

mpii logoMinerva of the Max Planck Society




Reading Group Algorithms (Summer 2012)

Kurt Mehlhorn and Carola Winzen


Deadline for the submission of the summaries is Friday, August 31 at 1 pm.


Wednesday, 4:15 pm to 5:45 pm

First meeting:

First Wednesday of the summer 2012 term, i.e., April 18.


024 on the ground floor in the MPI building (E1.4).


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 tak 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.


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.


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.

If you want credit for the course, please register with Carola by sending her a short mail.






April 18


Introduction to the reading group


April 25


Judea Pearl: Turing Award 2011


May 2

Danny Hermelin

Multiway Cut in FPT via Important Separators


May 9

Pawel Gawrychowski

De-amortizing Binary Search Trees


May 16

No reading group


May 23

Surender Baswana

Fully Dynamic Algorithm for Undirected Connectivity


May 30

Hans Raj Tiwary

Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds


June 6

Pavel Kolev

Conflict Packing Yields Linear Vertex-Kernels for k-FAST, k-dense RTI and a Related Problem


June 13

Carola Winzen

Query Complexities and Mastermind


June 20

Nicole Megow

Scheduling to meet deadlines: online algorithms and feasibility tests


Stephen Kobourov

How to extract true trajecories of a collection of ants


June 27

Andreas Schmid

2-Walks in 3-connected planar graphs


July 4

Matthias Mnich

Parameterized Complexity of the Clique Cover Problem


July 11

No reading group


July 18

Ralf Jung

On Buffon machines and numbers




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 Carola. 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.