Decoration

max planck institut
informatik

mpii logoMinerva of the Max Planck Society

   
 
 
 
 
 
 

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:

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.