Reading Group Algorithms
Seminar
Basic Information
Given by: | Kurt Mehlhorn, Daniel Vaz |
---|---|
Time: | Wednesday, 4:15 PM |
Room: | 024 (MPI-INF) |
First Meeting: | October 17 |
Credits: | 7 credit points |
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. |
Deadlines: | October 24rd: Topic Selection November 13th: HISPOS Registration and Date Selection February 23rd: Summary Submission |
Description
We will read (more or less) recent papers in theoretical computer science. The paper may be less recent if there is interesting follow-up work. In each session we have a regular presentation (40-50 minutes + discussion) of one paper. The reading group is open for all interested students and postdocs. Students aiming to get credit points must give a regular talk and write a short summary about the paper.
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, more precisely until February, 23rd. 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).
The reading group counts as a seminar in your study program. You can register by sending an e-mail to Daniel. Please make sure that you read the section on prerequisites above before you register.
News
Schedule
Date | Speaker | Topic | Reference |
---|---|---|---|
Oct 17 | Daniel Vaz | Introduction to the Reading Group | |
Bhaskar Ray Chaudhury | A Strongly Polynomial Algorithm for Linear Exchange Markets | [Oct17] | |
Oct 24 | Kurt Mehlhorn | A New Path from Splay to Dynamic Optimality | [Oct24] |
Oct 31 | --cancelled-- | ||
Nov 7 | Tim Oosterwijk | Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation | [Nov07] |
Nov 14 | Daniel Vaz | Euclidean spanners: Short, Thin and Lanky | [Nov14] |
Nov 21 | André Nusser | Customizable Route Planning in Road Networks | [Nov21] |
Nov 28 | |||
Dec 5 | Alkmini Sgouritsa | Barriers to Near-Optimal Equilibria | [Dec05] |
Dec 12 | Antonios Antoniadis | Competitively Chasing Convex Bodies | [Dec12] |
Dec 19 | Pavel Kolev | Low Rank Approximation: PTAS for Binary l0-rank-k | [Dec19] |
Jan 9 | Artin Saberpour Abadian | Fast fourier transforms: A tutorial review and a state of the art | [Jan09] |
Jan 16 | Daniel Radke | Refined Vertex Sparsifiers of Planar Graphs | [Jan16] |
Jan 23 | Nico Gründel | On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry | [Jan23] |
Jan 30 | Eunjin Oh | Clustering Problems on Sliding Windows | [Jan30] |
Feb 6 | Saeed Amiri | Important Cuts and their Applications | [Feb06] |
Papers
List of papers available for students.
Paper Title | Authors | Advisor(s) | Taken |
---|---|---|---|
Fast fourier transforms: A tutorial review and a state of the art | Pierre Duhamel, Martin Vetterli | X | |
Klaus Jansen, Lars Rohwedder | |||
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer | |||
Panayotis Mertikopoulos, Christos Papadimitriou, Georgios Piliouras | |||
C.J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee | |||
Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results | Anupam Gupta, Kunal Talwar, David Witmer | ||
Aleksander Mądry | |||
Near optimal bootstrapping of hitting sets for algebraic models | Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse | ||
Michael A. Bender, Martin Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, Shikha Singh | |||
Robert Krauthgamer, Inbal Rika | X | ||
Ryan Williams | X | ||
A Strongly Polynomial Algorithm for Linear Exchange Markets (Part 2) | Jugal Garg, László A. Végh | ||
|
|
References
Paper Title / Abstract of Talk | Authors | |
[Oct17] | Jugal Garg, László A. Végh | |
[Oct24] | Caleb Levy, Robert Tarjan | |
[Nov07] | Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation | Pieter Kleer, Guido Schäfer |
[Nov14] | Sunil Arya, Gautam Das, David Mount, Jeffrey Salowe, Michiel Smid | |
[Nov21] | Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck | |
[Dec05] | Tim Roughgarden | |
[Dec12] | Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, Mark Sellke | |
[Dec19] | Approximation Schemes for Low-Rank Binary Matrix Approximation Problems | Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh |
Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff | ||
[Jan09] | Fast fourier transforms: A tutorial review and a state of the art | Pierre Duhamel, Martin Vetterli |
[Jan16] | Robert Krauthgamer, Inbal Rika | |
[Jan23] | Ryan Williams | |
[Jan30] | Vladimir Braverman, Harry Lang, Keith Levin, Morteza Monemizadeh | |
[Feb06] | A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem | Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, Igor Razgon |