Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

Teaching

Reading Group Algorithms (A), Winter 2014/2015

Kurt Mehlhorn, Marvin Künnemann and Ruben Becker

Time: Wednesday, 4:15 pm to 5:45 pm
First meeting: First Wednesday of the Winter 2014/2015 term, i.e., 22nd October.
Room: 024 on the ground floor of 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 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:
  • If you want credit for the course, please register with Ruben and Marvin by sending them a short mail including your matriculation number (before October 29).
  • If you want credit for the course, please choose a paper from the below list and inform Ruben and Marvin by sending a short mail (by Nov 5).
  • Summaries are due on Sunday, March 1st.
Schedule:
Date Speaker Topic References
Oct 22 Introduction to the reading group
Marvin Künnemann Smoothed Complexity of the Simplex Method [Oct 22]
Oct 29 Ruben Becker Pi is in Log-Space [Oct 29]
Nov 5 Stephan Friedrichs A Practical Iterative Algorithm for the Art Gallery Problem [Nov 5]
Nov 12 Paresh Nakhe Robust Price of Anarchy Bounds via LP and Fenchel Duality [Nov 12]
Nov 19 Mayank Goswami Kakeya Sets in Finite Fields, Lines and Joints [Nov 19]
Nov 26 Kunal Dutta Discrepancy in arithmetic progressions [Nov 26]
Dec 3 Stefan Neumann Information Theoretical Cryptogenography [Dec 3]
Dec 10 Andreas Schmid On Graph Crossing Number and Edge Planarization [Dec 10]
Dec 17 Cancelled!
Jan 7 Marvin Künnemann Boolean Orthogonal Detection and the Polynomial Method in Algorithm Design [Jan 7]
Jan 14 Omar Darwish Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search [Jan 14]
Jan 21 Cancelled! [Jan 21]
Jan 28 Tobias Salzmann The power of deferral: maintaining a constant-competitive steiner tree online [Jan 28, 1]
Baris Cakar How to Write a 21st Century Proof [Jan 28, 2]
Feb 4 Kurt Mehlhorn Complexity of Linear Programming:
"Geometric random edge", "On sub-determinants and the diameter of polyhedra" 		[Feb 4]
Feb 11 Ruben Becker Judge: Don't Vote! [Feb 11]
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