Reading Group Algorithms
Seminar
Basic Information
Given by:  Kurt Mehlhorn, Daniel Vaz 

Time:  Wednesday, 4:15 PM 
Room:  024 (MPIINF) 
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 followup work. In each session we have a regular presentation (4050 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 email 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 NearOptimal Equilibria  [Dec05] 
Dec 12  Antonios Antoniadis  Competitively Chasing Convex Bodies  [Dec12] 
Dec 19  Pavel Kolev  Low Rank Approximation: PTAS for Binary l0rankk  [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: NearlyLinear vs BarelySubquadratic 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 FarachColton, 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 LowRank 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 FixedParameter Algorithm for the Directed Feedback Vertex Set Problem  Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, Igor Razgon 