Uni-Logo
Algorithms and Complexity
 

Algorithms and Complexity
Block Seminar - Winter Term 2022/23
Fabian Kuhn

 


Introductory Meeting: Tuesday, October 25, 13:15-14:00

The introductory meeting for the seminar will take place in the room 51-00-031 in building 51. It will be possible to attend the introductory meeting via zoom. The zoom link is here:

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.

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 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.

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 first-come-first-served 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 multiple-unicast instance?
2 Universally-optimal 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 single-pass semi-streaming 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 single-pass semi-streaming algorithm that given a graph G with maximum degree Delta, can output a proper coloring of G using any number of colors which is sub-exponential 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 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 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 end-result, 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 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 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.
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 Near-Optimal 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 schedule-length lower bound of Omega(congestion +dilation log n ) rounds, (b) a distributed algorithm that produces a near-optimal O(congestion+dilation log log n log n) round schedule, after O(dilation log^2 n) rounds of pre-computation.
13 Packet routing and job-shop 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 edge-simple 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 job-shop 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 information-theoretically 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 + 1-list 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 n-node 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 low-degree 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 + 1-list 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.