Teaching

Reading Group Algorithms (Summer 2012)

Kurt Mehlhorn and Carola Winzen

NEW:

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

Time:

Wednesday, 4:15 pm to 5:45 pm

First meeting:

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

Room:

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

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

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.

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

Schedule:

Date	Speaker	Topic	Reference
April 18	Carola	Introduction to the reading group
April 25	Kurt	Judea Pearl: Turing Award 2011	[25.4.]
May 2	Danny Hermelin	Multiway Cut in FPT via Important Separators
May 9	Pawel Gawrychowski	De-amortizing Binary Search Trees	[9.5.]
May 16		No reading group
May 23	Surender Baswana	Fully Dynamic Algorithm for Undirected Connectivity	[23.5.]
May 30	Hans Raj Tiwary	Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds	[30.5.]
June 6	Pavel Kolev	Conflict Packing Yields Linear Vertex-Kernels for k-FAST, k-dense RTI and a Related Problem	[6.6.]
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	[27.6.]
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	[18.7.]

References:

[25.4.] Judea Pearl Wins 2011 ACM Turing Award.
[9.5.] "De-amortizing Binary Search Trees" by Prosenjit Bose, Sébastien Collette, Rolf Fagerberg, and Stefan Langerman.
[23.5.] All of us know about the connectivity problem for undirected graph. The aim is to process a given undirected graph on n vertices and m edges to build a data structure so that any query of the form "Is there is path between u and v ?" can be answered efficiently. We all know a BFS/DFS based data structure for this problem which takes O(n+m) processing time, O(n) space, and O(1) query time. Let us consider a dynamic version of this problem: There is an undirected graph on n vertices under a sequence of edge deletions and insertion. The aim is to maintain an online data structure which can answer any connectivity query efficiently and handle any insertion or deletion of edge efficiently as well. Henzinger and King [STOC 1995, JACM 1999] designed a novel algorithm for this problem which takes expected amortized O(polylog n) time to process an edge deletion/insertion and answer any connectivity query in O(log n) time as well. The algorithm uses an efficient data structure for dynamic trees, and a couple of simple and novel ideas. In this talk, we shall also discuss the current state of the art as well as some open problems from the area of dynamic graph algorithms.
[30.5.] "Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds" by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf.
[6.6.], suggested by Anke van Zuylen "Conflict Packing Yields Linear Vertex-Kernels for k-FAST, k-dense RTI and a Related Problem" by Christophe Paul, Anthony Perez, and Stéphan Thomassé.
[27.6.], suggested by Jens M. Schmidt "2-Walks in 3-connected planar graphs" by Gao, Richter, Yu.
[18.7.], suggested by Reto Spöhel "On Buffon machines and numbers" by Philippe Flajolet, Maryse Pelletier, and Miehèle Soria.

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