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

DateSpeakerTopicReference
Oct 17Daniel VazIntroduction to the Reading Group
Bhaskar Ray ChaudhuryA Strongly Polynomial Algorithm for Linear Exchange Markets[Oct17]
Oct 24Kurt MehlhornA New Path from Splay to Dynamic Optimality[Oct24]
Oct 31--cancelled--
Nov 7Tim OosterwijkPotential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation[Nov07]
Nov 14Daniel VazEuclidean spanners: Short, Thin and Lanky[Nov14]
Nov 21André NusserCustomizable Route Planning in Road Networks[Nov21]
Nov 28
Dec 5Alkmini SgouritsaBarriers to Near-Optimal Equilibria[Dec05]
Dec 12Antonios AntoniadisCompetitively Chasing Convex Bodies[Dec12]
Dec 19Pavel KolevLow Rank Approximation: PTAS for Binary l0-rank-k[Dec19]
Jan 9Artin Saberpour AbadianFast fourier transforms: A tutorial review and a state of the art[Jan09]
Jan 16Daniel RadkeRefined Vertex Sparsifiers of Planar Graphs[Jan16]
Jan 23Nico GründelOn the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry[Jan23]
Jan 30Eunjin OhClustering Problems on Sliding Windows[Jan30]
Feb 6Saeed AmiriImportant Cuts and their Applications[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

X

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

Ryan Williams

Marvin Künnemann

X

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

[Nov07]

Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation

Pieter Kleer, Guido Schäfer

[Nov14]

Euclidean spanners: Short, Thin and Lanky

Sunil Arya, Gautam Das, David Mount, Jeffrey Salowe, Michiel Smid

[Nov21]

Customizable Route Planning in Road Networks

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

[Dec05]

Barriers to Near-Optimal Equilibria

Tim Roughgarden

[Dec12]

Competitively Chasing Convex Bodies

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

A PTAS for lp-Low Rank Approximation

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]

Refined Vertex Sparsifiers of Planar Graphs

Robert Krauthgamer, Inbal Rika

[Jan23]

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

Ryan Williams

[Jan30]

Clustering Problems on Sliding Windows

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