Teaching

Reading Group Algorithms (C), Summer 2013

Kurt Mehlhorn and Karl Bringmann

Time:

Wednesday, 4:15 pm to 5:45 pm

First meeting:

First Wednesday of the summer 2013 term, i.e., 17th 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:

Schedule:

Date	Speaker	Topic	References
Apr 17	Kurt and Karl	Introduction to the reading group
	Karl	Lower bounds based on the Exponential Time Hypothesis	[Apr17]
Apr 24	Rob van Stee	Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games	[Apr24]
May 1		Public Holiday (Tag der Arbeit/Workers' Day)
May 8	Parinya Chalermsook	Approximation Resistance from Pairwise Independent Subgroups	[May08]
May 15	Sayan Bhattacharya	Combinatorial Walrasian Equilibrium	[May15]
May 22	Erik Jan van Leeuwen	How bidimensionality connects approximation and parameterization on planar graphs	[May22]
May 29	Kurt Mehlhorn	Certifying Algorithms: 3-Edge-Connectivity of Graphs	[May29]
Jun 5	Mingji Xia	An introduction to counting complexity	[Jun5]
Jun 12	Artur Jez	A New Way To Solve Linear Equations	[Jun12]
Jun 19	Andreas Wiese	The Geometry of Scheduling	[Jun19]
Jun 26	Fabian Wobito	Strict Fibonacci Heaps	[Jun26]
Jul 3	Andrea Fischer	Eigenvalues of a Matrix in the Streaming Model	[Jul3]
Jul 10	Patrick Klitzke	Data Structures for Range Minimum Queries in Multidimensional Arrays	[Jul10]
Jul 17	Sandy Heydrich	A still better performance guarantee for approximate graph coloring	[Jul17]
Jul 24	Jan-Oliver Kaiser	Coevolutionary Opinion Formation Games	[Jul24]

References:

[Apr17] "Lower bounds based on the Exponential Time Hypothesis" by D. Lokshtanov, D. Marx, and S. Saurabh.
[Apr24] "Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games" by Y. Disser, A. E. Feldmann, M. Klimm, and M. Mihalák.
[May08] "Approximation Resistance from Pairwise Independent Subgroups" by Siu On Chan.
[May15] "Combinatorial Walrasian Equilibrium" by M. Feldman, N Gravin, and B. Lucier.
[May22] "The Bidimensionality Theory and Its Algorithmic Applications" by E. D. Demaine and M. Hajiaghayi.
[May29] In the first part of the talk, I will discuss the concept of certifying algorithms. In the second part of the talk, I will sketch a recent result obtained jointly with Adrian and Jens: A certifying algorithm for 3-edge-connectivity of graphs.
Abstract for first part
Abstract for second part: We present a linear time certifying algorithm that tests graphs for 3-edge-connectivity. If the input graph G is not 3-edge-connected, the algorithm returns a 2-edge-cut. If G is 3-edge-connected, the algorithm returns a construction sequence that constructs G from the graph with two nodes and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity.
[Jun5] Slides on "Complexity Dichotomies for Counting Problems" by S. Despotakis and A.-N. Göbel, and "Holographic Algorithms" by Leslie G. Valiant.
[Jun12] "A Randomized Algorithm for Linear Equations over Prime Fields" by P. Raghavendra.
[Jun19] "The Geometry of Scheduling" by N. Bansal and K. Pruhs.
[Jun26] [Pawel Gawrychowski] "Strict Fibonacci Heaps" by G. S. Brodal, G. Lagogiannis, and R. E. Tarjan.
[Jul3] [He Sun] "Eigenvalues of a Matrix in the Streaming Model" by A. Andoni and H. Nguyen.
[Jul10] [Pawel Gawrychowski] "Data Structures for Range Minimum Queries in Multidimensional Arrays" by H. Yuan and M. J. Atallah and "On Space Efficient Two Dimensional Range Minimum Data Structures" by G. S. Brodal, P. Davoodi, and S. S. Rao and "Two Dimensional Range Minimum Queries and Fibonacci Lattices" by G. S. Brodal, P. Davoodi, M. Lewenstein, R. Raman, and S. S. Rao.
[Jul17] [Andreas Karrenbauer] "A still better performance guarantee for approximate graph coloring" by M. M. Halldorsson.
[Jul24] [Martin Hoefer] "Coevolutionary Opinion Formation Games" by K. Bhawalkar, S. Gollapudi, and K. Munagala.

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