Uni-Logo
Algorithms and Complexity
 

Algorithms and Complexity
Block Seminar - Winter Term 2020/21
Fabian Kuhn

 


Introductory Meeting: Thursday, Nov 05, 12:15-14:00

The introductory meeting for the seminar will take place as a video conference by using the video conferencing system zoom. The information on how to join the zoom meeting is available on following page:

Algorithms and Complexity Seminar Zoom Information

Important note: This website can only be accessed from within the university network. This can be done either by accessing the internet via the university eduroam, or by establishing a VPN tunnel to the university network. Note that you have to cancel the VPN tunnel again before you enter the Zoom meeting.

The seminar will be held as a block seminar, all presentations will take place on one day (or on two half days) in the last three weeks of the semester . Once the list of students for the seminar is fixed, we will do a doodle poll to find the best possible day(s) for the presentations.

Topic

The main objective of this seminar is to provide an opportunity to learn about some of the exciting topics current theoretical computer science research, specifically the field of distributed computing, has to offer.

Requirements

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.

Assignment

In order to get a grade, students have to study and later present the content of a research paper. The slides and talk should be in English. The seminar will be held as a block seminar on one or two days towards the end of the semester. In order to pass, attendance to all talks on the seminar day is mandatory. After each presentation there will be a few minutes for questions and discussion.

To make the subsequent discussion broader and more interactive, each participant will be assigned two papers which are presented by other students. Even though you do not have to read those in-depth, you will have to prepare one or two question(s) for each of the two papers, the answer to which you might find interesting for yourself and/or the audience and ask your question after the respective talk.

Timeline

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.

  • Thursday, 5th of November (first week of the semester), 12:15 - 14:00: Introductory event.
  • Tuesday, 17th of November: Decide for a paper and notify us about your choice. Based on your choice you will be assigned a mentor soon after. Please send an email to Marc Fuchs with a list of your three prefered papers.
  • Before December 23rd: Have a first meeting with your mentor (you need to read the assigned literature and have a rough idea how to present it or ask according questions).
  • Roughly three weeks before the talk: Send an email to your mentor in which you explain the structure of your presentation in sufficient detail so your mentor can provide feedback.
  • At least one week before your talk: Discuss your (complete) slides with your mentor, so that he/she can give feedback.
  • Not later than a day before the presentation date: Hand in an electronic copy of your slides, and questions on the two assigned papers.
  • Date via Poll: Presentations.

Papers to be Presented on 18th of February

Paper List

The papers on the list will be assigned on a first-come-first-served basis.

No. Title Link Brief Description
1 Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs ArXiv The article considers a distributed model with a hybrid communication model. The communication in this model occurs via two modes. A local communication mode modeled by a graph, where only incident nodes can communicate. And a global mode where any two nodes may communicate at severely limited bandwidth. This paper considers the problem of computing shortest paths in local communication graphs that are sparse. .
2 Improved Hardness of Approximation of Diameter in the CONGEST Model Dagstuhl It is known that computing the diameter of a graph in the distributed setting using small messages requires at least near-linear time. This paper shows that even finding something better than a 11/6-approximation requires polynomial time.
3 Simple Parallel and Distributed Algorithms for Spectral Graph Sparsification ACM The efficient transformation of dense instances of graph problems to nearly equivalent sparse instances is a powerful tool in algorithm design. Spectral sparsifiers are sparse graphs that preserve within a (1+epsilon) factor the quadratic form x^T L(G) x, where L(G) is the Laplacian matrix of G and epsilon is a parameter of choice. The authors of this paper obtain the first distributed spectral sparsification algorithm in the CONGEST model along with other parallel and distributed implementations.
4 Improved Distributed Approximations for Maximum Independent Set ArXiv It is known that, in the distributed setting, finding a maximal independent set requires at least Omega(sqrt(log n / log log n)), even for randomized algorithms. A maximal independent set implies a Delta-approximation of the maximum independent set, where Delta is the maximum degree of the graph. This paper shows that finding an ((1+epsilon)Delta)-approximation of the maximum (even weighted) independent set can be done exponentially faster, in O(poly log log n) rounds, using small messages.
5 Distributed Dense Subgraph Detection and Low Outdegree Orientation ArXiv This paper shows that, in the distributed setting, “dense” subgraphs can be identified with a deterministic O(log n) time algorithm that uses large messages, or with a randomized O(log^3 n) time algorithm that uses small messages. Also, it is shown an efficient algorithm that orients edges such that every node has small outdegree.
6 Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs Dagstuhl It is known that, in the distributed setting, for all constant k, detecting if a graph contains a cycle of length exactly 2k requires at least Omega(sqrt(n)) for algorithms that use small messages. This paper, among other things, shows that 2k cycle detection, for k=3,4,5, can be solved in O(n^(1-1/k)).
7 An O(log^(3/2) n) Parallel Time Population Protocol for Majority with O(logn) States ACM In population protocols there are n agents that randomly interact with each other, and at each interaction they can update their state based on their own current state and the current state of the other agent. In the majority problem each agent starts with one of two possible inputs, and the goal is to let all agents know what is the input that is more frequent. This paper shows that, if the total number of possible states of an agent is allowed to be O(log n), then the majority problem can be solved with a total of O(n log^(3/2) n) random interactions.
8 Distributed Graph Problems through an Automata-theoretic Lens ArXiv This paper shows, among other things, that for a family of problems called LCLs, their distributed complexity is decidable efficiently if the network is an unlabeled path or cycle, meaning that we can take the description of the problem and automatically get what is the distributed time complexity of it, and an optimal algorithm for it.
9 Near Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ArXiv This article applies a surprisingly basic optimization technique (gradient descent) to compute (1+epsilon)-approximations for the so-called Transshipment problem in polylogarithmic number of rounds in various distributed models of computing (CONGEST, Broadcast Congested Clique, Streaming model). The much more basic single source shortest paths problem (SSSP) can be seen as a special case of the transshipment problem and this paper gives the best known algorithms in the same distributed models for the SSSP problem.
10 Deterministic Distributed Vertex Coloring in Polylogarithmic Time ArXiv This paper studies the vertex coloring problem. More precisely, consider a graph G=(V,E) where V is the set of nodes (or vertices/processors) and E is the set of edges (communication links between nodes), and let Delta be the maximum degree in G. This paper shows how to color the nodes of a graph G with Delta^{1+o(1)} colors such that each neighboring nodes have different colors using poly(log n) rounds.
11 Small Cuts and Connectivity Certificates: A Fault Tolerant Approach Dagstuhl This paper studies connectivity problems in the CONGEST model, where each edge can carry at most O(log n) bits of information in each round of communication. The paper is focused on two problems; distributed computation of small edge cuts; and the computation of sparse connectivity certificates. 1- Regarding the first problem, given a graph G with edge connectivity lambda, the goal is to identify at least one minimum cut, that is a collection of lambda edges whose removal disconnects the graph. To solve the problem, a graph sampling technique is employed that is usually used in the fault-tolerant network design context. 2- Regarding the second one, for a given unweighted n-vertex D-diameter graph G = (V, E) and integer lambda >= 1, a connectivity certificate is a subgraph H subset G satisfying that it is lambda-edge (or vertex) connected iff G is lambda-edge (or vertex) connected. The certificate is said to be sparse if H has O(lambda.n) edges.
12 Distributed Strong Diameter Network Decomposition ArXiv The authors answer an open problem and devise a randomised polylogarithmic time algorithm for constructing strong diameter network decompositions in the CONGEST model. Network decomposition is a powerful construct used to solve many different graph problems in the distributed setting. Although, similar results were previously known for the LOCAL model.
13 The Locality of Distributed Symmetry Breaking ArXiv In this paper, authors show algorithms for different problems related to symmetry breaking, that is, MIS, ruling sets, coloring, and matching.
14 Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems ArXiv In the distributed setting there are important problems the solution of which can be verified by each node in parallel in O(1) rounds, even though in order to find such solution each node has to spend omega(1) rounds. The usual complexity measure used to solve these problems is related to distance: how far must a node see in order to output its part of the solution? This paper considers a different complexity measure, that is volume: how many nodes must a node see in order to output its part of the solution?
15 Distributed Approximation on Graph Powers ArXiv Consider the following setting: Given a graph G, you are asked to solve a problem on G^2. In graph theory, the kth power G^k is obtained from G by connecting any two nodes in G via an edge if their distance in G is at most k. The authors of this paper investigate two fundamental graph problems, namely minimum vertex cover and minimum dominating set, in the above setting, where they achieve new approximation and lower bound results in the distributed CONGEST model.
16 Derandomizing Local Distributed Algorithms under Bandwidth Restrictions ArXiv The main result of this paper is a deterministic algorithm for the Maximal Independent Set (MIS) problem that runs in time O(D log^2(n)) in the CONGEST model, where D is the diameter of the graph. Together with a breakthrough from 2019, this yields a deterministic polylogarithmic CONGEST algorithm for MIS.
17 Distance-2 Coloring in the CONGEST Model ArXiv A distance-2 coloring of a graph is a coloring of the nodes such that nodes that are within distance 2 have different colors. While in the LOCAL model this problem can be easily reduced to the standard coloring problem, the situation is different if we restrict the message sizes. The authors give efficient deterministic and randomized distributed algorithms for this problem in the CONGEST model.
18 Near Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ArXiv They apply a surprisingly basic optimization technique (gradient descent) to compute (1+epsilon)-approximations for the so-called Transshipment problem in polylogarithmic number of rounds in various distributed models of computing. The much more basic single source shortest paths problem (SSSP) can be seen as a special case of the transshipment problem and this paper gives the best known algorithms for the same distributed models for SSSP.
19 Single Source Shortest Paths in the CONGEST Model With Improved Bound ACM This work considers the Single Source Shortest Paths (SSSP) in the CONGEST model. In this model we have a graph, where the nodes represent computational units that can communicate along edges with messages of small size. The goal is that each node learns its distance to some dedicated source node. It can be shown that this problem takes at least Omega(D+n^{1/2}) communication rounds, where n is the number of nodes and D is the diameter of the graph. This article gets very close to this lower bound by solving SSSP in O(D+n^{1/2}+D^{1/4})rounds.
22 Simple, Deterministic, Constant-Round Coloring in the Congested Clique ArXiv This paper is the last in a series of papers that looks a the distributed coloring problem in the so-called congested clique model of distributed computation. It gives a relatively simple deterministic constant-time algorithm for the problem, improving on a much more complicated previous randomized algorithm.
24 A lower bound for the distributed Lovasz Local Lemma ArXiv A lower bound for an important distributed graph problem (LLL) is presented. To achieve this goal, a lower bound for a simple problem, called Sinkless Orientation, is proved, using a technique called speedup simulation. Such technique has been later used, in other works, to prove lower bound for other problems as well. A simpler proof is provided by Chang et al.
26 Approximating s-t-minimum cuts in ~O(n^2) time ArXiv This article improves on random sampling techniques for approximately solving problems that involve cuts in graphs. The authors give a lineartime construction that transforms any graph on n vertices into an O(n log n)-edge graph on the same vertices whose cuts have approximately the same value as in the original graph.


Presentation

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. You should aim to give the audience knowledge about the key concepts and insights of the paper. We encourage you to deviate from the logical structure of the paper and strive for the most lucid presentation of the topic.

You may want to have a look at how to design slides (e.g. link 1, link 2, link 3). 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 one of the main objectives 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.

Evaluation

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.