Teaching

Reading Group Algorithms (A), Winter 2013/14

Kurt Mehlhorn and Karl Bringmann

Time:

Wednesday, 4:15 pm to 5:45 pm

First meeting:

First Wednesday of the winter 2013/14 term, i.e., 16th of 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:

Please register in HISPOS/LSF if you want credit for the course.

Schedule:

Date	Speaker	Topic	References
Oct 16	Kurt and Karl	Introduction to the reading group
	Bojana Kodric	Composable and Efficient Mechanisms	[Oct16]
Oct 23	Pawel Gawrychowski	Dynamic graph connectivity in polylogarithmic worst case time	[Oct23]
Oct 30	Geevarghese Philip	An O*(c^\|K\|) algorithm for the K-cycle problem using (simple) algebraic tools	[Oct30]
Nov 06	Parinya Chalermsook	Optimal Hierarchical Decompositions for Congestion Minimization in Networks	[Nov06]
Nov 13	Erik Jan van Leeuwen	Graph cut problems: the separators are important!	[Nov13]
Nov 20	He Sun	Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees	[Nov20]
Nov 27	Sankaran Anand	Centrality of trees for capacitated k-center	[Nov27]
Dec 04	Kurt Mehlhorn	The Geometry of Binary Search Trees	[Dec04]
Dec 11	Aruni Choudhary	Improved Implementation of Point Location in General Two-Dimensional Subdivisions	[Dec11]
Dec 18	Manan Gandhi	Optimal Partitioning for Dual Pivot Quicksort	[Dec18]
Jan 08	Ruben Becker	Max-Flows in Directed Graphs with Unit Capacities in less than O(m^{3/2})	[Jan08]
Jan 15	Anna Adamaszek	Polynomial time approximation schemes for the traveling repairman and other minimum latency problems	[Jan15]
Jan 22	Adithya Vadapalli	PRIMES is in P	[Jan22]
Jan 29	Daniel Vaz	Max flows in O(nm) time or better	[Jan29]
Feb 05	Karl Bringmann	Dependent Random Choice	[Feb05]

References:

[Oct16] [Martin Hoefer] "Composable and Efficient Mechanisms" by V. Syrgkanis and E. Tardos.
[Oct23] "Dynamic graph connectivity in polylogarithmic worst case time" by B. Lapron, V. King, and B. Mountjoy.
[Oct30] "Abusing the Tutte matrix: An algebraic instance compression for the K-set-cycle problem" by M. Wahlström.
[Nov06] "Optimal Hierarchical Decompositions for Congestion Minimization in Networks" by H. Racke.
[Nov13] "Parameterized graph separation problems" by D. Marx, "Fixed-parameter tractability of multicut parameterized by the size of the cutset" by D. Marx and I. Razgon, "Multicut is FPT" by N. Bousquet, J. Daligault, and S. Thomassé, "Treewidth reduction for constrained separation and bipartization problems" by D. Marx, B. O'Sullivan, and I. Razgon.
[Nov20] "Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees" by A. Marcus, D. Spielman, and N. Srivastava.
[Nov27] "Centrality of trees for capacitated k-center" by H.-C. An, A. Bhaskara, and O. Svensson, "LP Rounding for k-Centers with Non-uniform Hard Capacities" by M. Cygan, M. Hajiaghayi, and S. Khuller.
[Dec04] "The Geometry of Binary Search Trees" by E. Demaine, D. Harmon, J. Iacono, D. Kane, and M. Patrascu.
[Dec11] [Eric Berberich] "Improved Implementation of Point Location in General Two-Dimensional Subdivisions" by M. Hemmer, M. Kleinbort, and D. Halperin.
[Dec18] [Artur Jez] "Optimal Partitioning for Dual Pivot Quicksort" by M. Aumüller and M. Dietzfelbinger.
[Jan08] "Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back" by A. Madry.
[Jan15] "Polynomial time approximation schemes for the traveling repairman and other minimum latency problems" by R. Sitters.
[Jan22] [Michael Sagraloff] "PRIMES is in P" by M. Agrawal, N. Kayal, and N. Saxena.
[Jan29] [Pawel Gawrychowski] "Max flows in O(nm) time or better" by James B. Orlin.
[Feb05] "Dependent random choice" by J. Fox and B. Sudakov.

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.

More Courses of the Algorithms and Complexity Group