Algorithms and Complexity
Block Seminar  Winter Term 2022/23
Fabian Kuhn
Introductory Meeting: Tuesday, October 25, 13:1514:00
The introductory meeting for the seminar will take place in the room 5100031 in building 51. It will be possible to attend the introductory meeting via zoom. The zoom link is here:
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.
Topic
The main objective of the Algorithms and Complexity 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 indepth, 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.
The presentations will take place on Friday the 3rd of Febuary 2023. The time slot for each presentation will be 45 minutes, which consists of 35 minutes of presentation and 10 minutes of discussion (not necessarily in that order, questions can be asked during the presentation).
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.
 First two weeks of semester: Introductory event.
 By 20th 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 with your preference(s)
 By 16th of December: 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.
 February 03.02.2023: Presentations.
Paper List
We will soon provide a list with papers that can be presented in the seminar. The papers on the list will be assigned on a firstcomefirstserved basis.
No.  Title  Link  Brief Description  
1  Network Coding Gaps for Completion Times of Multiple Unicasts  ArXiv  In a graph with weight capacities that describes a network we want to deliver packets from a set of source nodes to their intended target nodes in the network (a.k.a. multiple unicasts). In a routing protocol, only packets that a node has already seen can be transmitted over edges. By contrast, a network coding protocol may send any function of the messages it has already seen (e.g. the XOR of two messages). This paper answers the following question: How much faster than routing can network coding be for any multipleunicast instance?  
2  Universallyoptimal distributed algorithms for known topologies  ACM  Library  This paper considers the CONGEST model of distributed computing, where nodes in a graph can communicate with each other in synchronous rounds by exchanging a small message over each edge per round. The input of a problem is typically distributed over all nodes in the network which makes it necessary to communicate to solve this problem. Solving such problems is often highly dependent on the topology of the graph. Most algorithms seek to minimize the runtime (number of rounds) for the worst possible topology, neglecting the fact that much faster solutions are possible on specific topologies. This paper looks into algorithms that are universally optimal, i.e., that achieve the (provably) best possible runtime for every topology.  
3  Deterministic Graph Coloring in the Streaming Model  ArXiv  Recent breakthroughs in graph streaming have led to the design of singlepass semistreaming algorithms for various graph coloring problems such as (delta + 1)coloring. These algorithms are all randomized in crucial ways and whether or not there is any deterministic analogue of them has remained an important open question in this line of work. The authors of this paper settle this fundamental question by proving that there is no deterministic singlepass semistreaming algorithm that given a graph G with maximum degree Delta, can output a proper coloring of G using any number of colors which is subexponential in Delta.  
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 Deltaapproximation 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  Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization  ArXiv  This paper presents significantly improved deterministic algorithms for some of the key problems in the area of distributed graph algorithms, including network decomposition, hitting sets, and spanners. As the most prominent endresult, the authors obtain a deterministic construction for O(log n)color O(log n log log log n) strong diameter network decomposition in O(log^3 n) rounds. This is the first construction that achieves almost log n in both parameters, and it improves on a recent line of exciting progress on deterministic distributed network decompositions.  
6  Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.  ArXiv  This paper deals with graph algorithms in the massively parallel computation (MPC) model, an abstract model to study parallel computations by large clusters of computers. The paper in particular contains an elegant algorithm to find large matchings in a graph exponentially faster than in other (standard) distributed models.  
7  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.  
8  Nearly Maximum Flow in Nearly Linear Time  ArXiv  In a network that is given by a graph with capacitated, undirected edges we want to solve a flow problem. Each node has a demand value (that might be negative for sources) that needs to be satisfied. The goal is to route flow over the edges such that the the demands are satisfied without exceeding edge capacities (by much). This work approaches this problem as a continuous optimization problem, essentially applying the gradient descent method to minimize edge congestion.  
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 socalled 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  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 faulttolerant network design context. 2 Regarding the second one, for a given unweighted nvertex Ddiameter graph G = (V, E) and integer lambda >= 1, a connectivity certificate is a subgraph H subset G satisfying that it is lambdaedge (or vertex) connected iff G is lambdaedge (or vertex) connected. The certificate is said to be sparse if H has O(lambda.n) edges.  
11  Distributed Graph Coloring Made Easy  Yannic Maus.  ArXiv  In this paper we present a deterministic CONGEST algorithm to compute an O(k delta)vertex coloring in O(delta/k)+log* n rounds, where delta is the maximum degree of the network graph and 1<=k<=O(delta) can be freely chosen. The algorithm is extremely simple: Each node locally computes a sequence of colors and then it "tries colors" from the sequence in batches of size k. Our algorithm subsumes many important results in the history of distributed graph coloring as special cases, including Linial's color reduction [Linial, FOCS'87], the celebrated locally iterative algorithm from [Barenboim, Elkin, Goldenberg, PODC'18], and various algorithms to compute defective and arbdefective colorings.  
12  NearOptimal Scheduling of Distributed Algorithms  Mohsen Ghaffari  MIT  Website  This paper studies the question of how to run many distributed algorithms, solving independent problems, together as fast as possible. Suppose that we want to run distributed algorithms A1, A2 . . . , Ak in the CONGEST model, each taking at most dilation rounds, and where for each network edge, at most congestion messages need to go through it, in total over all these algorithms. Generalizing the framework of LMR [22], we study scheduling general distributed algorithms and present two results: (a) an existential schedulelength lower bound of Omega(congestion +dilation log n ) rounds, (b) a distributed algorithm that produces a nearoptimal O(congestion+dilation log log n log n) round schedule, after O(dilation log^2 n) rounds of precomputation.  
13  Packet routing and jobshop scheduling in O(congestion+dilation) steps  F. T. Leighton, Bruce M. Maggs & Satish B. Rao  CMU  Website  In this paper, we prove that there exists a schedule for routing any set of packets with edgesimple paths, on any network, in O(c+d) steps, where c is the congestion of the paths in the network, and d is the length of the longest path. The result has applications to packet routing in parallel machines, network emulations, and jobshop scheduling  
14  Analyzing Network Coding Gossip Made Easy  Bernhard Haeupler  ArXiv  We give a new technique to analyze the stopping time of gossip protocols that are based on random linear network coding (RLNC). Our analysis drastically simplifies, extends and strengthens previous results. We analyze RLNC gossip in a general framework for network and communication models that encompasses and unifies the models used previously in this context. We show, in most settings for the first time, that it converges with high probability in the informationtheoretically optimal time. Most stopping times are of the form O(k + T ) where k is the number of messages to be distributed and T is the time it takes to disseminate one message. This means RLNC gossip achieves "perfect pipelining".  
15  Simple Contention Resolution via Multiplicative Weight Updates  Dagstuhl  We consider the classic contention resolution problem, in which devices conspire to share some common resource, for which they each need temporary and exclusive access. We prove that a simple strategy suffices to achieve a channel utilization rate of 1/e  O(epsilon), for any epsilon > 0. We prove that if the adversary jams J time slots, then this scheme will achieve channel utilization 1/e  epsilon, excluding O(J ) wasted slots. Results similar to these (Bender, Fineman, Gilbert, Young, SODA 2016) were already achieved, but with a lower constant efficiency (less than 0.05) and a more complex algorithm.  
16  Ultrafast Distributed Coloring of High Degree Graphs  ArXiv  We give a new randomized distributed algorithm for the delta + 1list coloring problem. The algorithm and its analysis dramatically simplify the previous best result known of Chang, Li, and Pettie [SICOMP 2020]. This allows for numerous refinements, and in particular, we can color all nnode graphs of maximum degree delta >= log2+ Omega(1) n in O(log* n) rounds. The algorithm works in the Congest model, i.e., it uses only O(log n) bits per message for communication. On lowdegree graphs, the algorithm shatters the graph into components of size poly(log n) in O(log* delta) rounds, showing that the randomized complexity of delta + 1list coloring in Congest depends inherently on the deterministic complexity of related coloring problems. 
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.