Reading Group Algorithms

Seminar

Basic Information

Given by:Kurt MehlhornRuben Becker, and Emanuele Natale
Time:Wednesday, 4:15 PM
Room:024 in E1.4 (MPII-Building)
First Meeting:April, 19
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 credits 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 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 Ruben. Please make sure that you read the section on prerequisites above before you register.

News

  • There will be no meeting on Jun, 14th.
  • The meeting on Jun, 7th will start at 5:15 PM.
  • The first meeting will be on April, 19th.

Schedule

DateSpeakerTopicReference
Apr, 19RubenIntroduction to the Reading Group
GuyA Distributed (2+ε)-Approximation for Vertex Cover in O(logΔ/εloglogΔ) Rounds[Apr19]
Apr, 26BojanaLearning and Efficiency in Games with Dynamic Population[Apr26]
May, 3GoravSuccinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds[May3]
May, 10KarlStreaming algorithms for embedding and computing edit distance in thelow distance regime[May10]
May, 17KavithaA Size-Popularity Tradeoff in the Stable Marriage Problem[May17]
May, 24PavelFaster spectral sparsification and numerical algorithms for SDD matrices[May24]
May, 31DanielInterchanging distance and capacity in probabilistic mappings[May31]
Jun, 7MarvinStrong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation[Jun7]
Jun, 14No Reading Group
Jun, 21Reading Group canceled
Jun, 28DavisThe Gyori-Lovasz theorem and Spanning Tree Congestion[Jun28]
Jul, 5JulianThe Weighted Matching Approach to Maximum Cardinality Matching[Jul5]
Jul, 12AnuragBoundaries of VP and VNP[Jul12]
Jul, 19Emanuele[Jul19]
Jul, 26AttilaThe Ziggurat Method for Generating Random Variables[Jul26]

Papers

This list is complete.

Paper TitleAuthorsAdvisorTaken
On computing the Fréchet distance between surfacesAmir Nayyeri and Hanzhong XuBhaskar Ray Chaudhury
The Weighted Matching Approach to Maximum Cardinality MatchingHarold N. GabowAndreas KarrenbauerX
Best-Response Dynamics in Combinatorial Auctions with Item BiddingPaul Dütting, Thomas KesselheimBojana Kodric
New approximations for broadcast scheduling via variants of α-point roundingSungjin Im, Maxim SviridenkoAntonios Antoniadis
Hopsets with Constant Hopbound, and Applications to Approximate Shortest PathsMichael Elkin, Ofer NeimanChristoph Lenzen
Irrational Guards are Sometimes NeededMikkel Abrahamsen, Anna Adamaszek, Tillmann MiltzowStephan Friedrichs
Twenty (simple) questionsYuval Dagan, Yuval Filmus, Ariel Gabizon, Shay MoranYun Kuen (Marco) Cheung
An SDP-Based Algorithm for Linear-Sized Spectral SparsificationYin Tat Lee, He SunPavel Kolev
On the power of algebraic branching programs of width twoEric Allender, Fengming WangChristian Ikenmeyer
Self-approaching paths in simple polygonsProsenjit Bose, Irina Kostitsyna, Stefan LangermanAruni Choudhary
Cortical Computation via Iterative ConstructionsChristos Papadimitriou, Samantha Petti, Santosh VempalaEmanuele Natale
When Neurons FailEl Mahdi El Mhamdi, Rachid GuerraouiEmanuele Natale
A Biological Solution to a Fundamental Distributed Computing ProblemYehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai, Ziv Bar-JosephEmanuele Natale
Fine-Grained Complexity Analysis of Two Classic TSP VariantsMark de Berg, Kevin Buchin, Bart M. P. Jansen, Gerhard WoegingerKarl Bringmann
On the complexity of the multivariate resultantBruno Grenet, Pascal Koiran, Natacha Portier Anurag Pandey
On the Complexity of Noncommutative Polynomial FactorizationV. Arvind, Pushkar S Joglekar, Gaurav RattanAnurag Pandey

References

Paper Title / Abstract of TalkAuthors
[Apr19]A Distributed (2+ε)-Approximation for Vertex Cover in O(logΔ/εloglogΔ) RoundsReuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman
[Apr26]Learning and Efficiency in Games with Dynamic PopulationThodoris Lykouris, Vasilis Syrgkanis, Éva Tardos
[May3]Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower BoundsMichael A. Forbes, Amir Shpilka, Ben Lee Volk
[May10]Streaming algorithms for embedding and computing edit distance in thelow distance regimeDiptarka Chakraborty, Elazar Goldenberg, Michal Koucky
[May17]A Size-Popularity Tradeoff in the Stable Marriage Problem Kavitha Telikepalli
[May24]Faster spectral sparsification and numerical algorithms for SDD matricesIoannis Koutis, Alex Levin, Richard Peng
[May31]Interchanging distance and capacity in probabilistic mappingsReid Andersen, Uriel Feige
[Jun7]Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch EvaluationRyan Williams
[Jun28]The Gyori-Lovasz theoremAlexander Hoyer, Robin Thomas
On spanning tree congestionChristian Löwenstein, Dieter Rautenbach, Friedrich Regen
[Jul5]The Weighted Matching Approach to Maximum Cardinality MatchingHarold N. Gabow
[Jul12]Boundaries of VP and VNPJoshua A. Grochow, Ketan D. Mulmuley, Youming Qiao
[Jul19]
[Jul26]The Ziggurat Method for Generating Random VariablesGeorge Marsaglia, Wai Wan Tsang