Reading Group Algorithms

Seminar

Postponed by 4 weeks!

Please note that on 11.3., the entire Saarland university has postponed the start of the semester by 4 weeks.  This also affects this course.  We will update the information below as soon as we can.

Basic Information

Given by:Karl Bringmann, Bhaskar Ray Chaudhury
Time:Wednesday, 4:15 PM
Room:E1.4 024
First Meeting:May 6
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.

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-60 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 tba (around August, 15th). 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 Bhaskar. Please make sure that you read the section on prerequisites above before you register.

News

  • The seminar will most likely be virtual. Talks will be given on standard teleconference systems such as Zoom. In exceptional cases of unstable internet connection, it is also possible to record your talk and submit a video.
  • The Zoom URL for the nineth meeting (on 1st July): https://cs-uni-saarland-de.zoom.us/j/98670829152

Schedule

DateSpeakerTopicReference
May 6Bhaskar

 

Introduction to the Reading Group

Finding Fair and Efficient Allocations

[May6]
May 13Karl

 

Approximating Text-to-Pattern Hamming Distances

[May13]
May 20Pieter

 

Recent Progress in the Area of Approximate Sampling and Counting

[May20]
May 27Golnoosh

 

A Strongly Polynomial Algorithm for Linear Exchange Markets

[May27]
June 3Laszlo Kozma

 

Many Visits TSP

[Jun3]
June 10Pascal

 

On the Price of Anarchy for Flows over Time

[Jun10]
June 17Lukas

Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds

[Jun 17]
June 24Jannik

 

Approximation Schemes for 0-1 Knapsack

[Jun24]
July 1Saurabh

 

Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time

[Jul01]
July 8Shreyas

 

Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization

[Jul08]
July 15Hossein

 

A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique

[Jul15]

 

Papers

List of papers available for students.

 

Paper TitleAuthorsAdvisor(s)Taken
Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner TreeJaroslaw Byrka, Fabrizio Grandoni, Afrouz Jabal AmeliPranabendu Misra No
On the Price of Anarchy for Flows over TimeJosé Correa, Andres Cristi and Tim OosterwijkPieter KleerNo
A Local-Search Algorithm for Steiner ForestMartin Groß, Anupam Gupta, Amit Kumar and Jannik MatusckeCorinna CoupetteNo
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower BoundsF.V. Fomin, D. Lokshtanov, I. Mihajlin, S. Saurabh and M. ZehaviPrafullkumar TaleNo
Approximation Schemes for 0-1 KnapsackTimothy ChanKarl BringmannNo
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update TimeShiri Chechik, Tianyi ZhangAndre NusserNo
Differentiation of Blackbox Combinatorial Solvers Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, Michal RolinekAndreas KarrenbauerNo
Polylogarithmic-Time Deterministic Network Decomposition and Distributed DerandomizationVáclav Rozhoň, Mohsen GhaffariChristoph LenzenNo
A Polynomial-Time Approximation Scheme for Facility Location on Planar GraphsVincent Cohen-Addad, Marcin Pilipczuk and Michal PilipczukSándor Kisfaludi-BakNo
A Strongly Polynomial Algorithm for Linear Exchange MarketsJugal Garg, László A. VéghBhaskar Ray ChaudhuryNo

References

 Paper Title / Abstract of TalkAuthors
[May6]Finding Fair and Efficient AllocationsSiddharth Barman, Sanath Kumar Krishnamurthy, Rohit Vaish
[May13]Approximating Text-to-Pattern Hamming DistancesTimothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat
[May20]Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a MatroidNima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant
[May27]A Strongly Polynomial Algorithm for Linear Exchange MarketsJugal Garg, Laszlo Vegh
[Jun3]A time- and space-optimal algorithm for the many-visits TSPAndré Berger, László Kozma, Matthias Mnich, Roland Vincze
[Jun10]On the Price of Anarchy of Flows over TimeJose Correa, Andres Cristi, Tim Oosterwijk
[Jun17]Computation of Hadwiger Number and Related Contraction Problems: Tight Lower BoundsFedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, Meirav Zehavi
[Jun24]Approximation Schemes for 0-1 KnapsackTimothy M. Chan