Algorithms and Complexity
Block Seminar - Summer Term 2022
Fabian Kuhn
Introductory Meeting: Thursday, April 28, 12:15-14:00
The introductory meeting for the seminar will take place in the video-conference-room 04-007 in building 106. It is also possible to attend the meeting via zoom. The information on how to join the zoom meeting is available on following page:
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 Wednesday the 22nd of July 2022. The seminar will start at 8:30 am, and will be finished at roughly 4:30 pm, depending on the number of presentations. The time slot for each presentation will be 40 minutes, which consists of 30 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.
- Thursday, 28th of April, 12:15 - 14:00: Introductory event.
- By May 13: 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)
- Until June 15: 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.
- 22nd of July 8:30 am to 4:30 pm: Presentations.
Paper List
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 | Dagstuhl | 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 | Exponentially Faster Shortest Paths in the Congested Clique | ArXiv | The Congested Clique model is a distributed model where any pair of nodes may communicate in order to solve a problem with an input that is distributed over all nodes, but the communication between a given pair of nodes is subject to bandwidth restrictions. The problem input in this case is a graph formed by the nodes in the network, where each node initially only knows its incident edges in that graph. The goal is that every node learns its distance to all other nodes in that graph, also known as the all pairs shortest paths (APSP) problem. This article gives approximations of APSP exponentially faster than all previous known solutions. | |
| 4 | taken |
ArXiv | ||
| 5 | taken |
ArXiv | In the distributed HYBRID model, communication occurs via two modes. A local mode modeled by a graph, where only adjacent nodes can communicate and a global mode where any two nodes may communicate at limited bandwidth. This paper derandomizes an existing protocol to broadcast messages in a given network and shows how this protocol can be applied to obtain (the first) deterministic algorithms for certain types of graph problems in the HYBRID model. | |
| 6 | Time-Optimal Construction of overlay networks | ArXiv | The Node Capacitated Clique (NCC) model, is a synchronous message passing model where each node (or computer) can send messages to any other node, but only very few such transactions can take place per node and time-step. In the standard NCC model it is assumed that nodes know the set of “contact-IDs” of all other nodes, which allows them to contact each other directly. By contrast, this paper considers the NCC0 (NCC-Zero) model where the set of IDs is not known in advance and each node only knows its neighbors of an arbitrary connected graph formed by all nodes. In order to contact a node u, a given node v has to first establish contact by learning u’s contact-ID via a third node w that is already known to v. The authors demonstrate that in such a more restrictive setting one can still construct an overlay network that facilitates all-to-all communication without knowing the whole set of IDs in advance. | |
| 7 | Distance Computations in the Hybrid Network Model via Oracle Simulations | Dagstuhl | In the distributed HYBRID model, communication occurs via two modes. A local mode modeled by a graph, where only adjacent nodes can communicate and a global mode where any two nodes may communicate at limited bandwidth. This article gives improved results for various shortest paths problems. In particular, they leverage the fact that nodes that have more than average degree (= number of local neighbors) can take control of their neighbors to increase their own bandwidth via the global communication mode, thereby allowing them to learn large parts of the input graph and act as oracles for other nodes. | |
| 8 | 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. | |
| 9 | 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. | |
| 10 | taken |
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. | |
| 11 | 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. | |
| 12 | 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. | |
| 13 | 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. | |
| 14 | taken |
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 | taken |
ArXiv | Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. The authors of this paper prove that these exponential gaps are necessary and establish connections between the deterministic and randomized complexities in the LOCAL model. Each result has a very compelling take-away message. | |
| 16 | taken |
Sciencedirect | Maximum independent set is of fundamental interest, both in practical and theoretical aspects, even on hypergraphs, where the maximum independent set problem is generalized. In this paper, the authors describe and analyze three different approaches to approximately solve the weighted and unweighted maximum independent set problem in bounded-degree hypergraphs: local search, greedy and partitioning. They also describe a general technique that reduces the worst case analysis of certain approximation algorithms on hypergraphs to their analysis on ordinary graphs and apply it to the local search and greedy algorithms. | |
| 17 | taken |
ArXiv | Graph coloring has been one of the central problems in the area of distributed graph algorithms for over three decades. The authors of this paper present a surprisingly simple deterministic distributed algorithm that improves on the state of the art considerably, and also leads to a faster randomized distributed algorithm. | |
| 18 | taken |
link | This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of optimizing the running time successful when an O(n) bound is achieved on an n-vertex network. The authors propose that a more sensitive parameter is the network's diameter Diam. This is demonstrated in the paper by providing a distributed Minimum-weight Spanning Tree algorithm whose time complexity is sub-linear in n, but linear in Diam. The result is achieved through the application of graph decomposition and edge elimination techniques that may be of independent interest | |
| 19 | taken |
link | This paper gives a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L) can be verified probabilistically in polynomial time using logarithmic number of random bits and by reading sublogarithmic number of bits from the proof. They discuss implications of this characterization; specifically, they show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard. | |
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.