Seminar Distributed Computing Reading Group
Winter Term 2023/24
Seminar topic: Distributed Lower Bound Techniques
Seminar description
We will present and discuss material (papers and lecture notes) on lowerbound techniques for distributed graph algorithms. We will meet weekly on Monday from 16:15 - 18:00. Each week, we will discuss one topic. A (tentative) schedule of topics that we will discuss will soon be published on this website. Each student has to lead the discussion on one of the topics. The focus will be on a detailed understanding of the content rather than on a polished presentation. The presentations can therefore be done on the board, slides are not mandatory.
Tentative Schedule
- Weekly seminar meeting: Monday, 16:15 - 18:00, room 051-03-026 (Building 51, 3rd floor)
We have a first introductory meeting Monday 23.10. at 16:15 in room 051-03-026 (Building 51, 3rd floor). In this meeting, we will discuss how we plan to run the seminar.
- 30.10.2023: Linial lower bound for 3 coloring paths and cycles
- 06.11.2023: Assignment of papers, Introduction to Communication Complexity I
- 13.11.2023: Introduction to Communication Complexity II
- 20.11.2023: (student presentation)
Discussion of paper Distributed Verification and Hardness of Distributed Approximation
by Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer
(presented by Aria Ranjbar and Shaun Saju , mentored by Fabian Kuhn) - 27.11.2023: (student presentation)
Discussion of paper Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
by Keren Censor-Hillel, Seri Khoury, Ami Paz
(presented by Wendelin Verstappen, Brian Michelson , mentored by Marc Fuchs) - 04.12.2023: (student presentation
Discussion of paper No Sublogarithmic-time Approximation Scheme for Bipartite Vertex Cover
by Mika Göös, Jukka Suomela
(presented by Vasile Ionut Miron and Jan Cichosz , mentored by Salwa Faour) - 11.12.2023: (student presentation)
Discussion of paper A Breezing Proof of the KMW Bound
by Corinna Coupette, Christoph Lenzen
(presented by Chenqi Hao and Haidari, Said Orfan , mentored by Attila Mályusz) - 18.12.2023: (student presentation)
Discussion of paper A Lower Bound for the Distributed Lovász Local Lemma
by Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto
(presented by Jonathan Pieper and Henrik Leisdon, mentored by Zahra Parsaeian ) - 08.01.2024: Break - No Seminar
- 15.01.2024: (student presentation)
Discussion of paper An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
by Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie
(presented by Fabian Bitzenhofer and Marcel Schuhmacher , mentored by Gustav Schmid ) - 22.01.2024: (student presentation)
Discussion of paper An Automatic Speedup Theorem for Distributed Problems
by Sebastian Brandt
(presented by Srikanth Shastry and Michel Mackert , mentored by Zahra Parsaeian) - 29.01.2024: NO SEMINAR
- 05.02.2024: (student presentation)
Discussion of paper Lower bounds for maximal matchings and maximal independent sets
by Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
(presented by Christian Armbruster and Felix Ruedlin , mentored by Marc Fuchs)