Reading Group Algorithms
Seminar
Basic Information
| Given by: | Kurt Mehlhorn, Marvin Künnemann and Ruben Becker |
|---|---|
| Time: | Wednesday, 4:15 PM |
| Room: | 024 in E1.4 (MPII-Building) |
| First Meeting: | April, 20 |
| 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. Sometimes this is preceded by a short presentation of another paper (up to 20 minutes). 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. 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.
Schedule
| Date | Speaker | Topic | Reference |
|---|---|---|---|
| Apr, 20 | Marvin and Ruben | Introduction to the Reading Group | |
| Thatchaphol Saranurak | Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture | [Apr20] | |
| Apr, 27 | Mayank Goswami | Lower and Upper Bounds for the Online Matrix-vector (OMv) Problem | [Apr27] |
| May, 4 | Erik Jan van Leeuwen | FPT in Geometric Intersection Graphs | [May4] |
| May, 11 | Andreas Schmid | Algebraic Algorithms for Linear Matroid Parity Problems | [May11] |
| May, 18 | Syamantak Das | Minimizing Flow-Time on Unrelated Machines | [May18] |
| May, 25 | Parinya Chalermsook | Finding a Large Clique in Graphs: Open Problems and Techniques | [May25] |
| Jun, 1 | Michael Dirnberger | SAT through the lens of Statistical Physics | [Jun1] |
| Jun, 8 | Malte Schledjewski | Fast Convergence of Regularized Learning in Games | [Jun8] |
| Jun, 15 | Pavel Kolev | Faster Online Matrix-Vector Multiplication | [Jun15] |
| Jun, 22 | Sandy Heydrich | A Tale of Two Dimensional Bin Packing | [Jun22] |
| Jun, 29 | Matthias Függer | On the Convergence of the Hegselmann-Krause System | [Jun29] |
| Jul, 6 | Azin Ghazimatin | Computing Nonsimple Polygons of Minimum Perimeter | [Jul6] |
| Jul, 13 | Denis Müller | Unit Interval Editing is Fixed-Parameter Tractable | [Jul13] |
| Jul, 20 | Talk cancelled! | ||
| Jul, 27 | Alexander Anisimov | Scaling Algorithms for Weighted Matching in General Graphs | [Jul27] |
Papers
This list is complete.
| Paper Title | Authors | Advisor | Taken |
|---|---|---|---|
| Unit Interval Editing is Fixed-Parameter Tractable | Yixin Cao | Erik Jan van Leeuwen | X |
| Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks | Leonid Barenboim | Christoph Lenzen | |
| A Logarithmic Additive Integrality Gap for Bin Packing | Rebecca Hoberg, Thomas Rothvoss | Andreas Wiese | X |
| Bipartite Perfect Matching is in quasi-NC | Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf | Gorav Jindal | |
| The Submodular Secretary Problem Goes Linear | Moran Feldman und Rico Zenklusen | Thomas Kesselheim | |
| Computing Nonsimple Polygons of Minimum Perimeter | Sándor P. Fekete, Andreas Haas, Michael Hemmer, Michael Hoffmann, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, Julian Troegel | Stefan Friedrich | X |
| Approximate Undirected Maximum Flows in O(mpolylog(n)) Time | Richard Peng | Andreas Karrenbauer | |
| Scaling Algorithms for Weighted Matching in General Graphs | Ran Duan, Seth Pettie, Hsin-Hao Su | Ruben Becker | X |
| Fast Convergence of Regularized Learning in Games | Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, Robert Schapire | Martin Hoefer | X |
| An Improved Discrete Bat Algorithm for Symmetric and Asymmetric Traveling Salesman Problems | Eneko Osaba, Xin-She Yang, Fernando Diaz, Pedro Lopez-Garcia, Roberto Carballedo | Maximilan John | |
| On a Natural Dynamics for Linear Programming | Damian Straszak, Nisheeth K. Vishnoi | Kurt Mehlhorn |
References
| Paper Title/Abstract of Talk | Authors | |
| [Apr20] | Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture | Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak |
| [Apr27] | New Unconditional Hardness Results for Dynamic and Online Problems | Raphael Clifford, Allan Grønlund, Kasper Green Larsen |
| Matrix-vector multiplication in sub-quadratic time: (some preprocessing required) | Ryan Williams | |
| [May4] | The talk will be a survey; Talk to Erik Jan for an outline. | |
| [May11] | Algebraic Algorithms for Linear Matroid Parity Problems | Ho Yee Cheung, Lap Chi Lau, Kai Man Leung |
| [May18] | Minimizing Flow-Time on Unrelated Machines | Nikhil Bansal, Janardhan Kulkarni |
| [May25] | The talk will not be based on one specific paper; here is an abstract: Maximum Clique has been studied intensively. Still, we do not know the answer to a very basic question, e.g: Given an n-vertex graph G with a guarantee that a clique of size log n is in there, can an algorithm find a super-constant size clique in polynomial time? | |
| [Jun1] | The talk will not be based on one specific paper; here is an abstract: Critical phenomena are everywhere, including computer science! The existence of phase transitions has deep consequences regarding the computational complexity and structure of solutions for various optimization or decision problems. As a result, dedicated concepts and methods from Statistical physics apply and can be used to gain new and surprising insights. In this talk my goal is to introduce you to the basic ideas of the "statistical physics approach" using the well-known satisfiability problem as an illustrative example. The talk will be mainly based on the following paper: Determining computational complexity from characteristic phase transitions | Remi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman and Lidror Trojansky |
| [Jun8] | Fast Convergence of Regularized Learning in Games | Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, Robert Schapire |
| [Jun15] | Faster Online Matrix-Vector Multiplication | Kasper Green Larsen, Ryan Williams |
| [Jun22] | A Tale of Two Dimensional Bin Packing | Nikhil Bansal, Andrea Lodi, Maxim Sviridenko |
| [Jun29] | On the Convergence of the Hegselmann-Krause System | Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle, Huy Nguyen |
| Inertial Hegselmann-Krause Systems | Bernard Chazelle, Chu Wang | |
| [Jul6] | Computing Nonsimple Polygons of Minimum Perimeter | Sándor P. Fekete, Andreas Haas, Michael Hemmer, Michael Hoffmann, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, Julian Troegel |
| [Jul13] | Unit Interval Editing is Fixed-Parameter Tractable | Yixin Cao |
| [Jul20] | A Logarithmic Additive Integrality Gap for Bin Packing | Rebecca Hoberg, Thomas Rothvoss |
| [Jul27] | Scaling Algorithms for Weighted Matching in General Graphs | Ran Duan, Seth Pettie, Hsin-Hao Su |