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

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

DateSpeakerTopicReference
Oct 17Daniel VazIntroduction to the Reading Group 
Oct 17Bhaskar Ray ChaudhuryA Strongly Polynomial Algorithm for Linear Exchange Markets[Oct17]
Oct 24Kurt MehlhornA New Path from Splay to Dynamic Optimality[Oct24]
Oct 31Daniel VazOptimal Euclidean spanners: really short, thin and lanky[Oct31]
Nov 7Tim OosterwijkPotential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation[Nov07]
Nov 14André NusserCustomizable Route Planning in Road Networks[Nov14]
Nov 21Pavel KolevTBA[Nov21]
Nov 28Saeed AmiriTBA[Nov28]
Dec 5[Dec05]
Dec 12[Dec12]
Dec 17[Dec17]
Jan 9[Jan09]
Jan 16[Jan16]
Jan 23[Jan23]
Jan 30Eunjin OhExact Distance Oracles for Planar Graphs with Failing Vertices[Jan30]
Feb 6[Feb06]

Papers

List of papers available for students.

 

Paper TitleAuthorsAdvisor(s)Taken

Fast fourier transforms: A tutorial review and a state of the art

Pierre Duhamel, Martin Vetterli

Attila Kinali-Dogan

X

On Integer Programming and Convolution

Klaus Jansen, Lars Rohwedder

Karl Bringmann

 

Local Computation: Lower and Upper Bounds

Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer

Christoph Lenzen

 

Cycles in adversarial regularized learning

Panayotis Mertikopoulos, Christos Papadimitriou, Georgios Piliouras

Emanuele Natale

 

A Nearly-linear Bound for Chasing Nested Convex Bodies

C.J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee

Antonios Antoniadis

 

Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results

Anupam Gupta, Kunal Talwar, David Witmer

Daniel Vaz

 

Computing Maximum Flow with Augmenting Electrical Flows

Aleksander Mądry

Andreas Karrenbauer

 

Near optimal bootstrapping of hitting sets for algebraic models

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

Nitin Saurabh

 

Bloom Filters, Adaptivity, and the Dictionary Problem

Michael A. Bender, Martin Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, Shikha Singh

Daniel Vaz

 

Refined Vertex Sparsifiers of Planar Graphs

Robert Krauthgamer, Inbal Rika

Daniel Vaz

 

On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry

Ryan Williams

Marvin Künnemann

 

A Strongly Polynomial Algorithm for Linear Exchange Markets (Part 2)

Jugal Garg, László A. Végh

Bhaskar Ray Chaudhury

 

 

 

 

 

 

 

 

 

References

 Paper Title / Abstract of TalkAuthors
[Oct17]

A Strongly Polynomial Algorithm for Linear Exchange Markets

Jugal Garg, László A. Végh

[Oct24]

A New Path from Splay to Dynamic Optimality

Caleb Levy, Robert Tarjan

[Oct31]

Optimal Euclidean spanners: really short, thin and lanky

Michael Elkin, Shay Solomon

[Nov07]

Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation

Pieter Kleer, Guido Schäfer

[Nov14]

Customizable Route Planning in Road Networks

Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck

[Nov21]

 

 

[Nov28]

 

 

[Dec05]

 

 

[Dec12]

 

 

[Dec17]

 

 

[Jan09]

 

 

[Jan16]

 

 

[Jan23]

 

 

[Jan30]

Exact Distance Oracles for Planar Graphs with Failing Vertices

Panagiotis Charalampopoulos, Shay Mozes, Benjamin Tebeka

[Feb06]