Time:

Thursday, 12:30 to 14:00

First meeting:

First Wednesday of the winter 2012/13 term, i.e., October 17.

Room:

024 on the ground floor of the MPI building (E1.4),
except on Nov 08 and Nov 22, where we are in room 001 of the MMCI building (E1.7)

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 the first 45 minutes, we will have short presentations of one or two different papers. In the second 45 minutes, we have a regular presentation (40 minutes + 5 minutes discussion) of one paper.
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 four weeks after the end of the semester. The presentation needs to be discussed with us at least one week before your scheduled talk in the reading group.

News:


Schedule:

Date 
Speaker 
Topic 
Reference 
Oct 17

Kurt and Karl

Introduction to the reading group



Karl

Changing base without losing space

[Oct17]

Oct 25

Anna Adamaszek

A PolylogarithmicCompetitive Algorithm for the kServer Problem

[Oct25]

Nov 1


Public Holiday (Allerheiligen/All Saints' Day)


Nov 8 room change!

Tobias Mömke

Approximating Graphic TSP by Matchings

[Nov8]

Nov 15

Pawel Gawrychowski

Orthogonal range searching on the RAM, revisited

[Nov15]

Nov 22 room change!

Kurt

Computing Equilibrium Prices for the ArrowDebreu Market Model

[Nov22]

Nov 29

Magnus Wahlström

Faster algorithms for Hamiltonian Cycle

[Nov29]

Dec 6

Ruben Becker

Map Graphs

[Dec06]

Dec 13

Pavel Kolev

Multiway spectral partitioning and higherorder Cheeger inequalities

[Dec13]

Dec 20

Martin Hoefer

Learning Algorithms for Interference Problems

[Dec20]

Jan 10

Petro Lutsyk

Polynomial Time Algorithms for Branching Markov Decision Processes and
Probabilistic Min(Max) Polynomial Bellman Equations

[Jan10]

Jan 17

Christos Orlis

Finding odd cycle transversals

[Jan17]

Jan 24

Matthias Mnich

Computing Correlated Equilibria in Multiplayer Games

[Jan24]

Jan 31

BachThi Dinh

ColorCoding

[Jan31]

Feb 7

Thomas Sauerwald

Balls into Bins Via Local Search

[Feb07]


References:

[Oct17] "Changing base without losing space" by Y. Dodis, M. Patrascu, and M. Thorup.
[Oct25] "A PolylogarithmicCompetitive Algorithm for the kServer Problem" by N. Bansal, N. Buchbinder, A. Madry, and S. Naor.
[Nov8] "Approximating Graphic TSP by Matchings" by Tobias Mömke and Ola Svensson.
[Nov15] "Orthogonal range searching on the RAM, revisited" by Timothy M. Chan, Kasper Green Larsen, and Mihai Patrascu.
[Nov22] "A Combinatorial Polynomial Algorithm for the Linear ArrowDebreu Market" by Ran Duan and Kurt Mehlhorn.
[Nov29] "Determinant Sums for Undirected Hamiltonicity" by Andreas Björklund.
[Dec06] [Jens M. Schmidt]
"Map graphs" by ZhiZhong Chen, Michelangelo Grigni, and Christos H. Papadimitriou.
[Dec13] [He Sun]
"Multiway spectral partitioning and higherorder Cheeger inequalities" by James R. Lee, Shayan Oveis Gharan, and Luca Trevisan.
[Dec20]
"Convergence Time of Power Control Dynamics" by J. Dams, M. Hoefer, and T. Kesselheim.
and
"On a game theoretic approach to capacity maximization in wireless networks" by E. Asgeirsson and P. Mitra.
[Jan10] [Kurt Mehlhorn]
"Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations" by Kousha Etessami, Alistair Stewart, and Mihalis Yannakakis.
[Jan17] [Geevarghese Philip]
"Finding odd cycle transversals" by Bruce A. Reed, Kaleigh Smith, and Adrian Vetta.
[Jan24]
"Computing Correlated Equilibria in Multiplayer Games" by Christos Papadimitriou and Tim Roughgarden.
[Jan31] [Geevarghese Philip]
"Colorcoding" by Noga Alon, Raphael Yuster, and Uri Zwick.
[Feb07]
"Balls into Bins Via Local Search" by Paul Bogdan, Thomas Sauerwald, Alexandre Stauffer, and He Sun.

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.
 [Kurt Mehlhorn]
"The Cell Probe Complexity of Dynamic Range Counting" by Kasper Green Larsen.
 [Kurt Mehlhorn]
"On Range Searching in the Group Model and Combinatorial Discrepancy" by Kasper Green Larsen.
 [Kurt Mehlhorn]
"3SAT Faster and Simpler" by Timon Hertli.
 [Kurt Mehlhorn]
"The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #Phardness of Approximation)" by Leslie Ann Goldberg and Mark Jerrum.
 [Kurt Mehlhorn]
"Differential Privacy: A Survey of Results" by Cynthia Dwork.
 [Kurt Mehlhorn]
"Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations" by Kousha Etessami, Alistair Stewart, and Mihalis Yannakakis.
 [Thomas Sauerwald]
"Balanced Allocations: The Weighted Case" by Kunal Talwar and Udi Wieder.
 [Thomas Sauerwald]
"Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance" by Keren CensorHillel, Bernhard Haeupler, Jonathan A. Kelner, and Petar Maymounkov.
 [Thomas Sauerwald]
"Approximating the Expansion Profile and Almost Optimal Local Graph Clustering" by Shayan Oveis Gharan and Luca Trevisan.
 [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]
"Distance Oracles beyond the ThorupZwick Bound" by Mihai Patrascu and Liam Roditty.
 [Pawel Gawrychowski]
"Approximate distance oracles" by Mikkel Thorup and Uri Zwick.
 [Pawel Gawrychowski]
"Data Structures for Range Minimum Queries in Multidimensional Arrays" by Hao Yuan and Mikhail J. Atallah.
 [Pawel Gawrychowski]
"Strict Fibonacci Heaps" by Gerth S. Brodal, George Lagogiannis, and Robert E. Tarjan.
 [Geevarghese Philip]
"Colorcoding" by Noga Alon, Raphael Yuster, and Uri Zwick.
 [Geevarghese Philip]
"Finding odd cycle transversals" by Bruce A. Reed, Kaleigh Smith, and Adrian Vetta.
 [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.
 [Magnus Wahlström]
"Deterministic parameterized connected vertex cover" by Marek Cygan.
 [Magnus Wahlström]
"Fast PolynomialSpace Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems" by Jesper Nederlof.
 [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.
 [Radu Curticapean]
"The parameterized complexity of counting problems" by Jörg Flum and Martin Grohe.
 [Radu Curticapean]
"Satisfiability Allows No Nontrivial Sparsification Unless The PolynomialTime Hierarchy Collapses" by Holger Dell and Dieter van Melkebeek.
 [Radu Curticapean]
"Exponential Time Complexity of the Permanent and the Tutte Polynomial" by Holger Dell, Thore Husfeldt, Daniel Marx, Nina Taslaman, and Martin Wahlen .
 [He Sun]
"Eigenvalues of a Matrix in the Streaming Model" by Alexandr Andoni and Huy Nguyen.
 [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.
 [Mingji Xia]
"Holographic Algorithms" by Leslie G. Valiant.
 [Mingji Xia]
"The Complexity of Weighted Boolean #CSP" by Martin Dyer, Leslie Ann Goldberg and Mark Jerrum.
