• Department 1: Algorithms and Complexity

max planck institut
informatik

Teaching

Reading Group Algorithms (SS 2011)

Kurt Mehlhorn and Carola Winzen

Time:

Tuesday (16:15-17:45)

First meeting:

19.04.2011

Room:

023 on the ground floor in the MPI building (E1.4)

Prerequisites:

Knowledge of algorithms and data structures. The reading group is intended for postdocs and PhD as well as master students in algorithms.

Content:

We will read recent papers in algorithms.

In the first 45 minutes, we will have short presentations of 2 different papers (not exceeding 15 minutes + 5 minutes for discussion). In the second 45 minutes, we have a regular presentation (40 minutes + 5 minutes discussion).

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 complete the following tasks: You choose yourself a paper which has been presented in a leading conference or journal in the last two years. You check appropriateness of the paper with Kurt and Carola. After carefully reading the paper, you give a regular talk (40 min. + 5 min. for discussion) on the content of the article and write a short summary (about 5 pages). The summary should be handed in no later than July, 31.

If you want credit for the course, please register with Carola by sending her a short mail.

Meetings:

19.4, 26.4, 3.5, 10.5, 17.5, 24.5, 31.5, 7.6., 21.6, 28.6, 5.7., 12.7., 19.7.

Schedule:

Date	Speaker	Topic	Reference
19.04.	Kurt and Carola	Introduction to the Reading Group and Schedule
19.04.	Megha Khosla and Reto Spöhel	Selected papers from SODA 2011	[1], [2], [3]
19.04.	Kurt Mehlhorn	Leslie Valiant - Winner of the ACM Turing Award 2010	[4]
26.04.	Karolina Soltys	CCC 2011 Best paper: "Non-Uniform ACC Circuit Lower Bounds" by Ryan Williams	[5]
26.04.	Richard Peifer	Problems in Voting design
26.04.	Ramprasad Saptharishi	Almost linear time approximate max-flow in undirected graphs. Based on the STOC 2011 Co-winner of the Best Paper Award by Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng	[6]
03.05.	Chandan Saha	When hardness of a problem implies easiness of another problem and vice versa
03.05.	Manish Kumar Narang	STOC 2004 Best Paper: "Expander Flows, Geometric Embeddings and Graph Partitioning" by Sanjeev Arora, Satish Rao, and Umesh Vazirani	[7]
10.05.	He Sun	"The Unified Theorem of Pseudorandomness" by Salil Vadhan	[8]
10.05.	Adrian Neumann	"Subcubic Equivalences Between Path, Matrix, and Triangle Problems" by Virginia Vassilevska Williams and Ryan Williams	[9]
10.05.	Richard Peifer	"A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method" by M. Schulze	[10]
17.05.	Reto Spöhel	Polynomial-time approximation schemes for geometric NP-hard problems.	[11], [12]
24.05.	Adrian Neumann	Follow-up on "Subcubic Equivalences Between Path, Matrix, and Triangle Problems" by Virginia Vassilevska Williams and Ryan Williams	[9]
24.05.	Timo Kötzing	Infinite Random Graphs	[13], slides: [14]
31.05.	Konstantinos Panagiotou	The Lovász Local Lemma	[15], [16]
07.06.	Karolina Soltys	On Communication Complexity and its Applications	[17],[18]
21.06.	Naveen Garg	Approximation Algorithms for graphical-TSP	[19]
21.06.	Cosmina Croitoru	"Top-K Color Queries for Document Retrieval" by Marek Karpinski and Yakov Nekrich	[20]
28.06.	Ramprasad Saptharishi	"Towards coding for maximum errors in interactive communication" by Mark Braverman and Anup Rao (STOC 2011)	[21]
28.06.	Olga Mykytiuk	"Top-k Ranked Document Search In General Text Databases" by J. Shane Culpepper, Gonzalo Navarro, Simon J. Puglisi, and Andrew Turpin (ESA 2010)	[22]
05.07.	Leelavathy Pandian	"Fast Routing in Very Large Public Transportation Networks using Transfer Patterns" by Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger,Chris Harrelson, Veselin Raychev, and Fabien Viger	[23]
12.07.	Chandan Saha	A brief introduction to Reed-Solomon codes
12.07.	Abdullah Al Heyari	"On Sunflowers and Matrix Multiplication" by Noga Alon, Amir Shpilka, and Chris Umans	[24]
19.07.	Kurt Mehlhorn	"On-line bipartite matching made simple" by Benjamin Birnbaum, Claire Mathieu	[25]
19.07.	Jonas Oberhauser	"Social networks spread rumors in sublogarithmic time" by Benjamin Doerr, Mahmoud Fouz, and Tobias Friedrich	[26]

References:

• [1] SODA 2011 List of Accepted Papers
• [2] On Belief Propagation Guided Decimation for Random k-SAT by Amin Coja-Oghlan.
• [3] On Buffon Machines and Numbers by Philippe Flajolet, Maryse Pelletier, and Michele Soria.
• [4] ACM 2010 Turing Award
• [5] Non-Uniform ACC Circuit Lower Bounds
• [6] Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
• [7] Expander Flows, Geometric Embeddings and Graph Partitioning
• [8] The Unified Theory of Pseudorandomness
• [9] Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• [10] A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method
• [11] S. Arora: Polynomial-time approximation schemes for Euclidean TSP and other geometric problems, FOCS '96.
• [12] J.Remy, R. Spöhel, A. Weißl: On Euclidean vehicle routing with allocation, WADS '07/CGTA '11.
• [13] Asymmetric Graphs by P. Erdős and A. Rényi.
• [14] Slides of Timo's talk.
• [15] Robin A. Moser: A constructive proof of the Lovász local lemma. STOC 2009: 343-350.
• [16] Heidi Gebauer, Tibor Szabó, Gábor Tardos: The Local Lemma Is Tight for SAT. SODA 2011: 664-675..
• [17] Impagliazzo, Williams: Communication complexity with synchronized clocks.
• [18] Karolina Soltys: The hardness of Median in the synchronized bit communication model.
• [19] Approximating Graphic TSP by Matchings by Tobias Mömke and Ola Svensson.
• [20] Marek Karpinski and Yakov Nekrich: Top-K Color Queries for Document Retrieval, SODA 2011, 401-411.
• [21] "Towards coding for maximum errors in interactive communication" by Mark Braverman and Anup Rao (STOC 2011).
• [22] "Top-k Ranked Document Search In General Text Databases" by J. Shane Culpepper, Gonzalo Navarro, Simon J. Puglisi, and Andrew Turpin (ESA 2010).
• [23] Fast Routing in Very Large Public Transportation Networks using Transfer Patterns" by Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger,Chris Harrelson, Veselin Raychev, and Fabien Viger (ESA 2010).
• [24] "On Sunflowers and Matrix Multiplication" by Noga Alon, Amir Shpilka, and Chris Umans.
• [25] "On-line bipartite matching made simple" by Benjamin Birnbaum, Claire Mathieu.
• [26] "Social networks spread rumors in sublogarithmic time" by Benjamin Doerr, Mahmoud Fouz, and Tobias Friedrich.

Papers:

We encourage you to pick yourself a paper that has been presented at a leading conference or journal in the last 2 years. We are happy to help you selecting an appropriate topic. In any case, please send us the title of your talk and a reference to the paper no later than 2 weeks (1 week for short presentations) before your scheduled presentation.

Copyright 2011 by Max-Planck-Institut Informatik | Impressum
page last modified Monday, July 18, 2011