News
Some UpdatesWritten on 25.05.22 (last change on 25.05.22) by Sebastian Brandt
First things first: there will be no lecture on June 20, and also no exercise class. In other words, you will have a full week for looking at some of the course content again or catching up with some of the material in case you missed a lecture or exercise class. Make use of it! As we had some… Read more
First things first: there will be no lecture on June 20, and also no exercise class. In other words, you will have a full week for looking at some of the course content again or catching up with some of the material in case you missed a lecture or exercise class. Make use of it! As we had some more interactive parts in the last lectures, the content covered in the lectures is currently not entirely synchronous with the lecture notes that are available for the respective lectures. In particular, in the last lecture (May 23) we covered Section 3.2 of Lecture Notes 4 and Section 1 of Lecture Notes 5. (When asked in the exercise class, I said something different, that's why I'm mentioning it explicitly.) Lastly, for everyone who missed it: in order to give a bit of encouragement for really working on the exercises and to increase participation in presenting the solutions, we will only provide written solutions for those questions for which some of you present a solution (or at least the crucial ideas leading to the solution) during the exercise class. That already worked nicely in the last exercise class, keep it up!
|
Exams, Resources, Solutions, and Lecture 2Written on 03.05.22 (last change on 03.05.22) by Sebastian Brandt
Here are some updates on various topics. The exam dates have been fixed. The exam will take place on Tuesday, August 30, 9:00-12:00. The re-exam is scheduled for Friday, October 7, 9:00-12:00. As mentioned in the lecture, some resources (books, lecture notes from other courses) have been… Read more
Here are some updates on various topics. The exam dates have been fixed. The exam will take place on Tuesday, August 30, 9:00-12:00. The re-exam is scheduled for Friday, October 7, 9:00-12:00. As mentioned in the lecture, some resources (books, lecture notes from other courses) have been added to the webpage, available here. For the time being, we will also provide at least some solutions for the exercises (again, here). They might not be fully-fledged solutions with all details, but they should suffice to remind you of what we discussed in the exercise class. They are intended precisely for this purpose, please don't consider them as a substitute for solving the exercises yourself. Being able to follow a solution presented to you and coming up with a solution yourself are two entirely different things, please don't make the mistake of assuming that the former suffices. As you may have noticed, also the lecture notes and slides for Lecture 2 have been added in the meantime. We will usually make the slides available before the respective lecture, in case you want to add some notes to the slides during the lecture. As always, some of these resources might be slightly updated at some point, e.g., to eliminate mistakes or better reflect the actual content covered during the lecture. The exercise sheet for Lecture 2 is also out now. Please note that an exercise question about lower bounds has been added on Monday evening, so please check whether you have the updated version. That's all for now, see you next Monday! |
Lecture 1Written on 25.04.22 (last change on 25.04.22) by Sebastian Brandt Thanks everyone for attending the first lecture and tolerating the technical mishaps! The lecture notes, slides (slightly edited), and the exercise sheet for Lecture 1 are all available here. Please note that for some lectures the content of the respective lecture notes might not be exactly aligned… Read more Thanks everyone for attending the first lecture and tolerating the technical mishaps! The lecture notes, slides (slightly edited), and the exercise sheet for Lecture 1 are all available here. Please note that for some lectures the content of the respective lecture notes might not be exactly aligned with the content that we manage to cover in that lecture (for instance, the lecture notes for Lecture 1 cover some content that we will only get to in Lecture 2). Regarding the exercise sheet, the "algorithm by Cole and Vishkin" mentioned in Exercise 1 is simply the 3-coloring algorithm we saw in the lecture. Apologies again for the technical issues we had today. As the source of the troubles were (merely) insufficiently charged transmitters and receivers, we can hope for a lecture without any technical problems next Monday. |
Distributed Graph Algorithms
In this course, we will study the theory of distributed message-passing algorithms in computer networks, abstracted as graphs. Our focus will be on fundamental local graph problems, such as computing a vertex coloring or a maximal matching. How many rounds of (synchronous) computation between the vertices of the graph do we need to solve these problems (or, equivalently, how far do the vertices have to see in the graph)? We will design algorithms, analyze their (distributed) time complexity, and prove lower bounds. Starting with the very basics, we will gradually work our way towards more complex algorithms and results, including exciting developments at the frontier of current research. Note that this is a theory course, i.e., we will mathematically design and analyze algorithms and prove impossibility results, but won't implement them practically.
At the end of the course, the students will have a good overview of distributed algorithms for local graph problems. They will know the fundamental techniques for designing distributed algorithms and will be able to combine them to create more involved algorithms. They know how to analyze the time complexity of such algorithms and prove lower bounds that no algorithm can beat.
Topics
If you want to know more about which topics we will cover in this course, here is a rough overview. Note that this outline might be subject to change.
- the LOCAL model and local complexity
- coloring directed paths and rooted trees
- coloring general graphs
- lower bounds for coloring
- solving problems on trees
- problems on power graphs and greedy problems
- maximal independent set and maximal matching
- randomized algorithms and shattering
- network decomposition and derandomization
- locally checkable problems
- distributed complexity theory
- sinkless orientation
- lower bounds via round elimination
Registration
Registration is open now! This course cannot accomodate more than 100 students. Technically, the slots will be handed out on a first-come-first-serve basis, but we expect the number of slots to be sufficient for everyone interested.
Prerequisites
There are no formal prerequisites for this course, but a general interest in graph theory and designing/analyzing algorithms as well as a basic understanding of probabilities and algorithmic analysis (e.g., O-notation) will be helpful.
Lectures
There will be one lecture per week, taking place on Mondays, 10:00 (c.t.) - 12:00. The first lecture is on April 25. In principle, the course will be hybrid, i.e., you can attend physically or online. However, it is strongly recommended that you attend the lectures (and exercise classes) in person unless there are medical reasons for you not to do so. Physical attendance is preferred not only because there is always the danger of technical issues that impair or prevent the broadcast of the lecture, but also because we will have questions and discussions during the lecture, which you might (partially) miss if you are not there in person. Unfortunately, if you attend in person, you will have to wear a mask in the lecture hall.
The lectures will take place in building E9 1 (CISPA), room 0.05 (lecture hall ground floor) and are broadcast via zoom (disclaimer). For zoom access details, see below. To allow for unconstrained interaction (and to increase attendance), there will be no recordings of the lectures. However, we will provide lecture notes.
Exercises
Accompanying the lectures, we will have one exercise sheet for (almost) each lecture, and a weekly tutorial on Mondays, 16:00 (c.t.) - 18:00, in which we will have time to discuss the solutions to the exercises and potential questions from the lectures. The exercise sheet is released here on the day of the lecture, then you have a week to solve the exercises, and the tutorial for the exercise sheet is on the subsequent Monday. The exercises are not graded, but it is highly recommended to solve the exercises and attend the tutorial as this is an essential step in becoming familiar with the course content and being well-prepared for the exam.
Like the lectures, the tutorial will take place in building E9 1 (CISPA), room 0.05 (lecture hall ground floor). Again, access via zoom will be possible (for now, barring technical incidents), but physical attendance is even more recommended as there will be (even) more interaction than in the lectures. The first tutorial will take place on May 2. The mask mandate also applies to the tutorial.
Exam
Your grade for the course is determined via an exam taking place at the end of the course. The exam will be on Tuesday, August 30, 9:00-12:00. We will also have a re-exam, scheduled for Friday, October 7, 9:00-12:00. Even if you pass the exam, you are allowed to participate in the re-exam to improve your grade.
Zoom Access
The zoom access details are available under the materials tab (for registered students only).
Mattermost
As a forum for communication and discussion, we will use a Mattermost instance. You can sign up via the link provided in the materials tab (for registered students only).
Resources
A list of resources (books, lecture notes from other courses) is available here. Regarding the mentioned books (and their availability), please see also the literature page provided by the campus library for computer science and mathematics.