Time:

Wednesday, 4:15 pm to 5:45 pm

First meeting:

First Wednesday of the Winter 2014/2015 term, i.e., 22nd 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 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:

 If you want credit for the course, please register with Ruben and Marvin by sending them a short mail including your matriculation number (before October 29).
 If you want credit for the course, please choose a paper from the below list and inform Ruben and Marvin by sending a short mail (by Nov 5).
 Summaries are due on Sunday, March 1st.

Schedule:

Date 
Speaker 
Topic 
References 
Oct 22


Introduction to the reading group



Marvin Künnemann

Smoothed Complexity of the Simplex Method

[Oct 22]

Oct 29

Ruben Becker

Pi is in LogSpace

[Oct 29]

Nov 5

Stephan Friedrichs

A Practical Iterative Algorithm for the Art Gallery Problem

[Nov 5]

Nov 12

Paresh Nakhe

Robust Price of Anarchy Bounds via LP and Fenchel Duality

[Nov 12]

Nov 19

Mayank Goswami

Kakeya Sets in Finite Fields, Lines and Joints

[Nov 19]

Nov 26

Kunal Dutta

Discrepancy in arithmetic progressions

[Nov 26]

Dec 3

Stefan Neumann

Information Theoretical Cryptogenography

[Dec 3]

Dec 10

Andreas Schmid

On Graph Crossing Number and Edge Planarization

[Dec 10]

Dec 17


Cancelled!


Jan 7

Marvin Künnemann

Boolean Orthogonal Detection and the Polynomial Method in Algorithm Design

[Jan 7]

Jan 14

Omar Darwish

Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search

[Jan 14]

Jan 21


Cancelled!

[Jan 21]

Jan 28

Tobias Salzmann

The power of deferral: maintaining a constantcompetitive steiner tree online

[Jan 28, 1]


Baris Cakar

How to Write a 21st Century Proof

[Jan 28, 2]

Feb 4

Kurt Mehlhorn

Complexity of Linear Programming: "Geometric random edge", "On subdeterminants and the diameter of polyhedra"

[Feb 4]

Feb 11

Ruben Becker

Judge: Don't Vote!

[Feb 11]


References:

 [Oct 22] "Beyond Hirsch Conjecture: Walks On Random Polytopes And Smoothed Complexity of the Simplex Method" by Roman Vershynin
 [Oct 29] "Pi is in LogSpace" by Chee Yap
 [Nov 5] "The Quest for Optimal Solutions for the Art Gallery Problem: A Practical Iterative Algorithm" by Davi C. Tozoni, Pedro J. de Rezende and Cid C. de Souza
 [Nov 12] "Robust Price of Anarchy Bounds via LP and Fenchel Duality" by Janardhan Kulkarni and Vahab Mirrokni
 [Nov 19] "On the size of Kakeya sets in finite fields" by Zeev Dvir and "On Lines and Joints" by Haim Kaplan, Micha Sharir, Eugenii Shustin
 [Nov 26] "Discrepancy in arithmetic progressions" by Jiri Matousek, Joel Spencer.
 [Dec 3] "Information Theoretical Cryptogenography" by Sune K. Jakobsen.
 [Dec 10] "On Graph Crossing Number and Edge Planarization" by Julia Chuzhoy, Yury Makarychev and Anastasios Sidiropoulos
 [Jan 7] "More Applications of the Polynomial Method to Algorithm Design" by A. Abboud, R. Williams and H. Yu
 [Jan 14] "Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search" by M. Patrascu and M. Thorup
 [Jan 21] "Guarding Art Galleries by Guarding Witnesses" by KyungYong Chwa, ByungCheol Jo, Christian Knauer, Esther Moet, Rene van Oostrum and ChanSu Shin
 [Jan 28, 1] "The power of deferral: maintaining a constantcompetitive steiner tree online" by Albert Gu, Anupam Gupta and Amit Kumar.
 [Jan 28, 2] "How to Write a 21st Century Proof" by Leslie Lamport.
 [Feb 4] "Geometric Random Edge" by Friedrich Eisenbrand and Santosh Vempala and "On subdeterminants and the diameter of polyhedra" by Nicolas Bonifas, Marco Di Summa, Friedrich Eisenbrand, Nicolai Hähnle and Martin Niemeier
 [Feb 11] "Judge: Don't Vote!" by Michel Balinski and Rida Laraki

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 Ruben and Marvin.
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.

[Andreas Wiese] "The power of deferral: maintaining a constantcompetitive steiner tree online" by Albert Gu, Anupam Gupta and Amit Kumar.
 [Michael Kerber] "Low rank approximation and regression in input sparsity time" by Kenneth L. Clarkson and David P. Woodruff.
 [Erik Jan van Leeuwen] "Designing FPT algorithms for cut problems using randomized contractions" by Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk and Michal Pilipczuk.

[Christoph Lenzen] "How to Write a 21st Century Proof" by Leslie Lamport.
 [Andreas Karrenbauer] "An AlmostLinearTime Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations" by Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia and Aaron Sidford.
 [Yi Li] "Sparse Fourier Transform in Any Constant Dimension with NearlyOptimal Sample Complexity in Sublinear Time" by P. Indyk and M. Kapralov.

[Marvin Künnemann] "Information Theoretical Cryptogenography" by Sune K. Jakobsen

[Kurt Mehlhorn] "ALITHEIA: Towards Practical Verifiable Graph Processing" by Yupeng Zhang, Charalampos Papamanthou and Jonathan Katz
 [Ruben Becker] "Using PetalDecompositions to Build a Low Stretch Spanning Tree" by Ittai Abraham and Ofer Neiman

[Stephan Friedrichs] "Guarding Art Galleries by Guarding Witnesses" by KyungYong Chwa, ByungCheol Jo, Christian Knauer, Esther Moet, Rene van Oostrum and ChanSu Shin
 [Parinya Chalermsook] "Constructive discrepancy minimization for convex sets" by Thomas Rothvoß
 [Antonios Antoniadis] "Minimum Makespan Scheduling with Low Rank Processing Times" by Aditya Bhaskara, Ravishankar Krishnaswamy, Kunal Talwar and Udi Wieder
