Teaching

Reading Group Algorithms, Summer 2015

Kurt Mehlhorn, Marvin Künnemann and Ruben Becker

Time:

Wednesday, 4:15 pm to 5:45 pm

First meeting:

First Wednesday of the Summer 2015 term, i.e., 22nd April in room 023.

Room:

024 on the ground floor of the MPI building (E1.4) usually, and room 023 on Apr, 22.

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 each session we have a regular presentation (40-60 minutes + discussion) of one paper. Sometimes this is preceded by a short presentation of another paper (up to 20 minutes). 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 two weeks after the end of the semester. 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).

News for students:

Summaries are due on Friday, August 14th.

Schedule:

Date	Speaker	Topic	References
Apr 22	Marvin and Ruben	Introduction to the reading group
	Alexander Kobel	Certified Computation of Planar Morse-Smale Complexes of Smooth Functions	[Apr 22]
Apr 29	Kurt Mehlhorn	Still Simpler Way of Introducing Interior-Point method for Linear Programming	[Apr 29]
May 6	Daniel Vaz	Mimicking Networks and Succinct Representations of Terminal Cuts	[May 6]
May 13	Andreas Schmid	Dynamic Planar Embeddings of Dynamic Graphs	[May 13]
May 20	Pavel Kolev	Spectral Sparsification of Random-Walk Matrix Polynomials	[May 20]
May 27	Parinya Chalermsook	Approximating independent sets in sparse graphs	[May 27]
Jun 3	Arnur Nigmetov	Extendability of continuous maps is undecidable	[Jun 3]
Jun 10	Hai Dang Tran	Median Filtering is Equivalent to Sorting	[Jun 10]
Jun 17	Marc Roth	Shortest Two Disjoint Paths in Polynomial Time	[Jun 17]
Jun 24	Arijit Ghosh	Simple Proofs of Classical Theorems in Discrete Geometry via the Guth-Katz Polynomial Partitioning Technique	[Jun 24]
Jul 1	Michael Kerber	Sampling-based Algorithms for Optimal Motion Planning	[Jul 1]
Jul 8	Manfred Warmuth	The blessing and the curse of the multiplicative updates
Jul 15	Kunal Dutta	Communication is bounded by root of rank; A direct proof for Lovett's bound on the communication complexity of low rank matrices	[Jul 15]
Jul 22	Marvin Künnemann	The Simplex Algorithm is NP-mighty	[Jul 22]
Jul 29	Ruben Becker	Lower-Stretch Spanning Trees	[Jul 29]

References:

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 Ruben and Marvin. 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