Algorithms and Complexity

Distributed and Parallel Algorithms
Seminar - Winter Term 2018/19
Fabian Kuhn


Seminar Topic

The main objective of the theory of computation seminar is to provide an opportunity to learn about some of the exciting topics current theoretical computer science research has to offer. We plan to organize the seminar every winter term.

Administrative information

In order to get a grade, students have to study and later present the content of a research paper and each student also has to hand in a short written report about the paper (see details below). The seminar will be held as a block seminar on a day towards the end of the semester. In order to pass, attendance to all talks on the seminar day is mandatory. Your slides and talk should be in English. The presentation should last 30 minutes plus about 10 minutes of discussion.

We will meet the first time in the 2nd week of the semester, on Wednesday, October 24, at 12:15. room 106-00-007.


The course is mainly directed towards Master students and 3rd year Bachelor students (and interested PhD students) of computer science or mathematics. There are no specific requirements, but students should be interested in mathematical and algorithmic questions and basic mathematical maturity is expected.

Written Report: You will have to write a report of at least one page. The report should be a critical discussion of the paper. For example: Why is the paper interesting? Do you see any particular strengths or any weaknesses? Can the results be applied in practice or what would one need to change so that the results become practical? Do you see any interesting questions for follow-up research? Do you know any practical or theoretical work that is based on the paper? For the last part we strongly encourage some additional literature research.

In addition, every student who participates in the seminar will be assigned two papers which are presented by other students. You will need to prepare (and hand in before the seminar day) three questions for each of the two papers.


We require the following steps to ensure a good quality of the talks and hope that these will result in a good grade for you.

  • Until November 13: Decide for a paper. (please send an email with your preference(s))
  • Until December 11: Have a first meeting with your mentor (you need to read the assigned literature and have some idea on how to present it before this meeting).
  • Before Christmas: Send an email to your mentor in which you describe you plan to structure your presentation.
  • At least 1 week before your talk: Discuss your (complete) slides with your mentor, so that he/she can give feedback.
  • One day before the presentation date: Hand in your report, an electronic copy of your slides, and the question on the two assigned papers.
  • to be determined: Presentation

Paper List

  1. Achlioptas, Gouleakis, Iliopoulos - Local Computation Algorithms for the Lovasz Local Lemma
    Student: - Mentor: -
  2. Assadi - Sublinear Algorithms for Delta+1 Vertex Coloring
    Student: Daniel Fertmann Mentor: -
  3. Ghaffari - Distributed MIS via All-to-All Communication
    Student: - Mentor: -
  4. Ghaffari, Gouleakis, Mitrovic - Improved Massively Parallel Computation Algorithms for MIS, Matching, Vertex Cover
    Student: - Mentor: -
  5. Censor-Hillel, Dory - Distributed Spanner Approximation
    Student: Albert Lidel Mentor: -
  6. Dory - Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
    Student: - Mentor: -
  7. Grossman, Parter - Improved Deterministic Distributed Construction of Spanners
    Student: Patrick Bühler Mentor: -
  8. Agarwal, Ramachandran, King, Pontecorvi - A deterministic Algorithm for Exact weighted APSP in n^(3/2) Rounds
    Student: Julian von Tschammer Mentor: -
  9. Bamas, Esperet - Distributed Coloring of Graphs with an Optimal Number of Colors
    Student: Maya Schöchlin Mentor: -
  10. Censor-Hillel, Parter - Derandomizing Local Distributed Algorithms under Bandwidth Restrictions
    Student: - Mentor: -
  11. Censor-Hillel, Khoury, Paz - Quadratic and Near-Quadtratic Lower Bounds for the CONGEST Model
    Student: Pascal Bachor Mentor: -
  12. Elkin - Distributed Exact Shortest Paths in Sublinear Time
    Student: - Mentor: -
  13. Elkin, Neiman - Distributed Strong Diameter Decomposition
    Student: Manex Lizaso Mentor: -
  14. Fischer - Improved Deterministic Distributed Matching via Rounding
    Student: Hema Hanifa rani Mukka Mentor: -
  15. Fischer, Ghaffari - Sublogarithmic Distributed Algorithms for Lov´asz Local Lemma, and the Complexity Hierarchy
    Student: - Mentor: -
  16. Gaffari, Harris, Kuhn - On Derandomizing Local Distributed Algorithms
    Student: - Mentor: -
  17. Barenboim, Tzur - Distributed Symmetry-Breaking with Improved Vertex-Averaged Complexity
    Student: - Mentor: -

Your talk


Above we have a series of suggested papers which will be assigned on a first-come-first-serve basis. All presentations should cover the motivation for the problem, put it into a historic context (e.g., quickly stating the results of previous papers) as well as some technical parts of the paper in detail. Assume that the other participants know nothing about the subject. You are not supposed to present the whole paper, but just the aspects that were most intriguing to you. We encourage you to deviate from the logical structure of the paper and strive for the most lucid presentation of the topic. Furthermore you may want to have a look at how to design slides (e.g. link 1, link 2, -- link 3 (chapter 5), link 4). -We further expect the presentation to motivate a lively discussion. Your presentation should not be a mere transfer of knowledge, but inspire an animated debate among the seminar participants.


We encourage discussion during and after a presentation as a main objective of this seminar. The extent to which your own presentation instigates discussion as well as your own participation in the other presentations will influence your grade in this course.


Below are the criteria according to which we judge a good presentation.

  • Motivated Talk

    The speaker was motivated and kept the audience interested throughout the presentation.

  • Clearly Explained

    The speaker made the material clear and comprehensible.

  • Knowledge Transfer

    The (awake and participating) audience learned something.

  • Difficulty

    The presentation was (too) difficult, easy, or just right to follow.

  • Prior Knowledge

    The speaker did not assume inappropriate prior knowledge.

  • Structure

    The presentation had a clear concept and discernible structure.

  • Encouraged Participation

    The speaker actively encouraged participation and successfully led the discussion.