max planck institut
informatik

# Teaching

## Reading Group Algorithms (WS 2011/12)

Time:

Thursdays, 16:15 - 17:45

First meeting:

First week of WS 2011/12, i.e., Thursday, October 20.

Room:

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

Prerequisites:

Knowledge of algorithms and data structures. The target audience of this reading group are master students, PhD students as weel as postdocs.

Content:

We will read (more or less) recent papers in theoretical computer science. The paper may be less recent only if there is interesting follow-up 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.

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

Schedule:

 Date Speaker Topic Reference 20.10. Kurt and Carola Introduction to the Reading Group and Schedule [20.10. 1] Carola Winzen Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity [20.10. 2] 27.10. Kurt Mehlhorn Solving sparse symmetric diagonally dominant linear systems [27.10. 1], [27.10. 2], [27.10. 3] 3.11. Danny Hermelin Kernelization Lower Bounds Shay Moran A puzzle I will talk about next week 10.11. Shay Moran A set theoretical formulation of "almost everywhere" Konstantinos Panagiotou Hunting the Random k-sat Threshold [10.11. 1] 17.11. Cosmina Croitoru Argumentation Frameworks [17.11. 1] Ruben Becker Analysis of Agglomerative Clustering [17.11. 2] 24.11. Xavier Pérez Giménez Graphs with Average Degree Smaller than 30/11 are burning slowly [24.11. 1] Rom Pinchasi On some principles of plane geometry [24.11. 2] 1.12. Bernhard Schommer SAT Modulo Theory [1.12.] 8.12. Nabil Mustafa The Multiplicative Weights Technique in Discrete Geometry [8.12. 1] 15.12. Fahimeh Ramezani Black-Box Randomized Reductions in Algorithmic Mechanism Design [15.12. 1] Svilen Dimitrov Private Circuits: Securing Hardware against Probing Attacks [15.12. 2] 22.12. No reading group. Happy holidays! 12.1. Alexey Pospelov Small Private Circuits [12.1. 1] 19.1. Yash Raj Shrestha Linear Problem Kernels for Planar Graph Problems with Small Distance Property [19.1. 1] Marvin Künnemann On independent sets in random graphs [19.1. 2] 26.1. Igor Stassiy Noisy interpolation of sparse polynomials, and applications [26.1. 1] 2.2. Kaloyan Rusev The Mastermind Game and Variants [2.2. 1] Krishna Narasimhan Discrepancy Minimization [2.2. 2], [2.2. 3] 9.2. Manish Kumar Narang An improved LP-based approximation for steiner tree [9.2. 1] Yury Bakkanouski Sustaining the Internet with Hyperbolic Mapping [9.2. 2]

References:

Papers:

A list of papers which are still available for presentation in the reading group follows. We may add more papers. 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 these papers, please write us a short mail or come to our office. 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.