Reading Group Algorithms
| Instructors: | Robert Elsässer, Sebastian Forster |
| Type: | 2 SE |
| ECTS: | 5 |
| Curriculum: | Master Informatik |
| Time and Place: | Monday, 16:00-17:30, T.04 |
Schedule
| Date | Speaker | Paper | Material |
|---|---|---|---|
| 18.11. | Sebastian Forster | [For+20] | slides notes |
| 25.11. | Gregor Bankhamer | [BES19] | slides |
| 02.12. | Tim Ungerhofer | [BCCK19] | slides |
| Ouafae Lachhab | [Arg+07] | slides | |
| 09.12. | Paul Huber | [GS18] | slides |
| 16.12. | Sara Seidl | [KX16] | |
| 13.01. | Hugo Platzer | [AAE08] | slides |
| 20.01. | Sophie Reischl | [NS16] | |
| 27.01. | Alexander Nemetz-Fiedler | [Ali+17] | slides |
List of Papers
- [Ali+17] Time-Space Trade-offs in Population Protocols
Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, Ronald L. Rivest
In Proc. of the Symposium on Discrete Algorithms (SODA), 2017 - [AAE08] Fast Computation by Population Protocols With a Leader
Dana Angluin, James Aspnes, David Eisenstat
Distributed Computing 21(3): 183-199, 2008 - [BCCK19] Dynamic DFS in Undirected Graphs: Breaking the O(m) Barrier
Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, Shahbaz Khan
SIAM Journal on Computing (SICOMP) 48(4): 1335-1363, 2019 - [BES19] Local Fast Rerouting with Low Congestion: A Randomized Approach
Gregor Bankhamer, Robert Elsässer, Stefan Schmid
In Proc. of the International Conference on Network Protocols (ICNP), 2019 - [For+20] Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak, Liu Yang, Sorrachai Yingchareonthawornchai
In Proc. of the Symposium on Discrete Algorithms (SODA), 2020 - [GS18] Fast Space Optimal Leader Election in Population Protocols
Leszek Gasieniec, Grzegorz Stachowiak
In Proc. of the Symposium on Discrete Algorithms (SODA), 2018 - [KX16] Simple Parallel and Distributed Algorithms for Spectral Graph Sparsification
Ioannis Koutis, Shen Chen Xu
ACM Transactions on Parallel Computing (TOPC) 3(2): 14:1-14:14, 2016 - [NS16] Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
Ofer Neiman, Shay Solomon
ACM Transactions on Algorithms (TALG) 12(1): 7:1-7:15, 2016 - [Arg+07] An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms
Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro
SIAM Journal on Computing (SICOMP) 36(6): 1672-1695, 2007
Guidelines
- Talk of 45 minutes (+ 15 minutes for questions)
- Seminar paper of around 12 pages, due on February, 29
- Language: English