Teaching

Reading Group Algorithms (B), Summer 2014

Kurt Mehlhorn and Karl Bringmann

Time:

Wednesday, 4:15 pm to 5:45 pm

First meeting:

First Wednesday of the summer 2014 term, i.e., 16th of April.

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
Apr 16	Kurt and Karl	Introduction to the reading group
	Sayan Bhattacharya	Fully dynamic maximal matching in O(log n) update time	[Apr16]
Apr 23	Karl Bringmann	Approximation Algorithms for the Diameter of Sparse Graphs - and a Lower Bound	[Apr23]
Apr 30	Parinya Chalermsook	Cut-Matching Games and Applications	[Apr30]
May 07	Marvin Künnemann	Cryptogenography	[May07]
May 14	Patrick Nicholson	Cell probe lower bounds for succinct data structures	[May14]
May 21	Michal Adamaszek	Robust Satisfiability of Systems of Equations	[May21]
May 28	Nabil H. Mustafa	Approximating k-Median via Pseudo-Approximation	[May28]
Jun 04	Kunal Dutta	New Constructive Aspects of the Lovasz Local Lemma	[Jun04]
Jun 11	Kurt Mehlhorn	Truthful and Near-Optimal Mechanism Design via Linear Programming	[Jun11]
Jun 18	Antonios Antoniadis	Minimizing Weighted Flow Time	[Jun18]
Jun 25	Arijit Ghosh	Constructive Discrepancy Minimization by Walking on The Edges	[Jun25]
Jul 02	Wanchote Jiamjitrak	Improved Approximation Algorithm for Two-Dimensional Bin Packing	[Jul02]
Jul 09	Kurt Mehlhorn	Practice Talk of Erasmus Lecture
Jul 16	Thatchaphol Saranurak	A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time	[Jul16]
Jul 23	Geevarghese Philip	On problems without polynomial kernels	[Jul23]

References:

[Apr16] "Fully dynamic maximal matching in O(log n) update time" by S. Baswana, M. Gupta, and S. Sen.
[Apr23] "Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs" by L. Roditty and V. Vassilevska Williams, "Better Approximation Algorithms for the Graph Diameter" by S. Chechik, D. Larkin, L. Roditty, G. Schoenebeck, B. Tarjan, and V. Vassilevska Williams.
[Apr30] "Graph Partitioning using Single Commodity Flows" by R. Khandekar, S. Rao, and U. Vazirani, "Edge Disjoint Paths in Moderately Connected Graphs" by S. Rao and S. Zhou, "A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2" by J. Chuzhoy and S. Li.
[May07] "Cryptogenography" by J. Brody, S. K. Jakobsen, D. Scheder, and P. Winkler.
[May14] "Cell Probe Lower Bounds For Succinct Data Structures" by A. Golynski.
[May21] "Robust Satisfiability of Systems of Equations" by P. Franek and M. Krcal.
[May28] "Approximating k-Median via Pseudo-Approximation" by S. Li and O. Svensson.
[Jun04] "New Constructive Aspects of the Lovasz Local Lemma" by B. Haeupler, B. Saha, and A. Srinivasan.
[Jun11] "Truthful and Near-Optimal Mechanism Design via Linear Programming" by R. Lavi and C. Swamy.
[Jun18] "Minimizing Weighted Flow Time" by N. Bansal and K. Dhamdhere, "Weighted Flow time does not admit O(1)-competitive algorithms" by N. Bansal and H.-L. Chan.
[Jun25] "Constructive Discrepancy Minimization by Walking on The Edges" by S. Lovett and R. Meka.
[Jul02] [Andreas Wiese] "Improved Approximation Algorithm for Two-Dimensional Bin Packing" by N. Bansal and A. Khan.
[Jul16] [Andreas Karrenbauer] "A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time" by J. A. Kelner, L. Orecchia, A. Sidford, and Z. Allen Zhu.
[Jul23] "On problems without polynomial kernels" by H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin.

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.
This list is complete.

More Courses of the Algorithms and Complexity Group