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 followup work.
In each session we have a regular presentation (4060 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_kBound 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: 3EdgeConnectivity 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

JanOliver 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_kBound 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 3edgeconnectivity of graphs.
Abstract for first part
Abstract for second part: We present a linear time certifying algorithm that tests graphs for 3edgeconnectivity.
If the input graph G is not 3edgeconnected, the algorithm returns a 2edgecut. If G is
3edgeconnected, 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 3edgeconnectivity.
[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.
 [Kurt Mehlhorn]
"Beyond the Flow Decomposition Barrier" by A. V. Goldberg and S. Rao.
 [Kurt Mehlhorn]
"Nearly Maximum Flows in Nearly Linear Time" by Jonah Sherman.
 [He Sun]
"A combinatorial construction of almostramanujan graphs using the zigzag product" by A. BenAroya and A. TaShma.
 [He Sun]
"Max Cut and the Smallest Eigenvalue" by Luca Trevisan.
 [He Sun]
"ST Connectivity on Digraphs with a Known Stationary Distribution" by KaiMin Chung, Omer Reingold, and Salil Vadhan.
 [Rob van Stee]
"On the Value of Job Migration in Online Makespan Minimization" by Susanne Albers and Matthias Hellwig.
 [Rob van Stee]
"Optimizing Social Welfare for Network Bargaining Games in the Face of Unstability, Greed and Spite" by T.H. Hubert Chan, Fei Chen, and Li Ning.
 [Rob van Stee]
"Finding Social Optima in Congestion Games with Positive Externalities" by Bart de Keijzer and Guido Schäfer.
 [Rob van Stee]
"On MinPower Steiner Tree" by Fabrizio Grandoni.
 [Rob van Stee]
"A 5Approximation for Capacitated Facility Location" by Manisha Bansal, Naveen Garg, and Neelima Gupta.
 [Martin Hoefer]
"Matroid Prophet Inequalities" by R. Kleinberg and S. Weinberg.
 [Andreas Karrenbauer]
"Approximating Maximum Clique by Removing Subgraphs" by Uriel Feige.
 [Erik Jan van Leeuwen]
"Bidimensionality and EPTAS" by Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh.
 [Erik Jan van Leeuwen]
"Bidimensionality and Geometric Graphs" by Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh.
 [Erik Jan van Leeuwen]
"Planar FDeletion: Approximation and Optimal FPT Algorithms" by Fedor Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh.
 [Erik Jan van Leeuwen]
"Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time" by H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof.
 [Jens M. Schmidt]
"Light Subgraphs in planar graphs of Minimum Degree 4 and EdgeDegree 9" by B. Mohar, R. Skrekovski, and H.J. Voss.
 [Pawel Gawrychowski]
"Max flows in O(nm) time or better" by James B. Orlin.
 [Pawel Gawrychowski]
"Distance Oracles beyond the ThorupZwick Bound" by Mihai Patrascu and Liam Roditty.
 [Pawel Gawrychowski]
"Approximate distance oracles" by Mikkel Thorup and Uri Zwick.
 [Geevarghese Philip]
"A 4k^2 kernel for feedback vertex set" by Stéphan Thomassé.
 [Geevarghese Philip]
"On problems without polynomial kernels" by Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin.
 [Eric Berberich]
"Deconstructing approximate offsets" by E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova.
 [Eric Berberich]
"Motion Planning via Manifold Samples" by O. Salzman, M. Hemmer, B. Raveh, and D. Halperin.
 [Eric Berberich]
"Improved Implementation of Point Location in
General TwoDimensional Subdivisions" by M. Hemmer, M. Kleinbort, and D. Halperin.
 [Mingji Xia]
"The Complexity of Weighted Boolean #CSP" by Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum.
 [Parinya Chalermsook]
"Approximating kMedian via PseudoApproximation" by Shi Li and Ola Svensson.
 [Parinya Chalermsook]
"A Polylogarithmic Approximation Algorithm for EdgeDisjoint Paths with Congestion 2" by Julia Chuzhoy and Shi Li.
 [Parinya Chalermsook]
"Approximating Bin Packing within O(log OPT * log log OPT) bins" by Thomas Rothvoss.
 [Parinya Chalermsook]
"Hypercontractivity, SumofSquares Proofs, and their Applications" by B. Barak, F. Brandao, A. Harrow, J. Kelner, D. Steurer, and Y. Zhou.
 [Parinya Chalermsook]
"Approximability and Proof Complexity" by Ryan O'Donnell and Yuan Zhou.
