# Seminar: Gems of Theoretical Computer Science

## Seminar, Winter Term 2019/20

The seminar based on a set of selected papers and textbook sections that demonstrate the beauty of problem solutions in the field of Theoretical Computer Science. We will find out that the preoccupation with sophisticated proof techniques, elegant arguments and surprising constructions is highly enjoyable. The seminar is inspired by the book "Perlen der Theoretischen Informatik " by Uwe Schöning, in which he presents a collection of results demonstrating highlights of Theoretical Computer Science. Of course, the selection of seminar topics is affected by the supervisor’s taste and research area. The seminar is expected to take place as a block seminar at the end of the lecture period.

## Lecturer

## Modul

- Seminar I / Seminar II

## Dates & Deadlines

- First meeting (distribution of topics):
**October 9**^{th}, 2019, 16:30, F0.530, Fürstenallee 11 - First meeting with advisor (You are expected to have read the paper, and come with concrete questions):
**November 14**^{th}-15^{th}, 2019 - Submission deadline of the 0-version of
__seminar thesis__(see Step II below):

**December 16**^{th}, 2019

(We strongly recommend to give at least part of the thesis to your advisor**in advance to this deadline**, in consultation with him) - Submission deadline of the
__reviews__(see Step III below):

**January 13**^{th}, 2020 - Start test presentations (see Step IV below):
**January 24**^{th}, 2020 - Submission deadline of the
__final version__of the seminar thesis:**January 27**^{th}, 2020 - Block Seminar, Presentation of your work (see Step I below):
**February 6**^{th}-7^{th}, 2020 (date changed !)

## Topics and Registrations

The topics (see below) are given in the first meeting. Reservations or defaults of issues are not possible. **You should have a look at the topics (see below) and respective papers before the first meeting and make your mind up about your topic preferences. **The application for this Seminar is managed through the Jupyter System. Klick here for more information on the application procedure.

## Grading and Demands

I) __Presentation__

60 minutes presentation.

15 minutes discussion and questions.

Your audience: Your fellow students.

As a minimal requirement, the presentation should motivate your model, formally introduce the problem, explain the necessary techniques, and provide insight into the necessary algorithms and their analysis (i.e., with proofs!). Some ideas e.g. "Scientific Working"

II) Seminar thesis

Essay of length 12 to 20 pages written according to the standards of a scientific paper. **Submitting work of others is cheating and a violation of academic plagiarism rules, which is a serious offense. We use a commercial, Internet-based plagiarism detection service to check your submissions. **Also the **simple copying of the original work** into the own thesis causes the **failure of the seminar**.

**III) Reviews**

- Peer review procedure similar to scientific publications
- You submit your thesis (paper) at easychair.org
- Some (2) peers (other students) review your submission

• Read and understand the submitted paper

• Criticize your paper

• Make recommendations on how to improve

• Be honest, polite, and helpful when writing your reviews - The reviews you write will influence your final grade
- The reviews you receive will not influence (but your final version)
- Each student has to write
**2 reviews**(each**1-2 pages**)

**IV) ****Test run of your presentatio****n**

- Do a test run with your presentation.
- Meet in groups of approx. 3-4 students
- Give each other feedback
- Negotiate date yourselves
- Tell us when and where you plan to meet (mandatory!)
- We can organize a room for you if necessary

We expect your active participation (as opposed to mere attendance) at all presentations of this seminar.

We will grade the **quality of the presenta**

**and the**

**tion****quality of the**

**e****ssay**/

**seminar thesis**individually. You have to pass (i.e., 4.0 or better) each part individually to pass this course. Note that commitment, diligence, and compliance with our deadlines will be taken into account.

## Remarks

**General**

Each topic has one or several references that should be understood as starting points for your research. Hence, it is very likely that you will need further papers or textbooks to fully understand your topic. The actual content of your seminar thesis as well as your seminar talk should be discussed with your adviser.

It is your responsibility to contact your adviser and schedule appointments with them early enough. We strongly recommend you to discuss questions regarding the topic, the composition, and the structure of your written seminar thesis with your adviser. The same holds for your seminar talk. Note that finding an appointment directly before your thesis' submission or seminar talk cannot be guaranteed, since the advisers need to arrange their appointments with their own teaching and research.

If you are looking for additional research papers, the following links might be helpful:

**Seminar Thesis**

We expect an* essay of length 12 to 20 pages* written according to the standards of a scientific paper. A simple summary of the referenced literature is insufficient. We expect you to identify the important ideas and proofs of the referenced literature and present them in a correct and appropriate way. The mandatory typesetting for your thesis is LaTeX (see below for details). All citations must be marked as such and referenced with their origin. Plagiarism directly leads to failure of the seminar. Note that plagiarism not only includes copies from the original literature, but also copies from other authors (e.g., other seminar theses) or translations of them.

**Title and Abstract**

Create a brief abstract that summarizes the problem and the main results. An abstract is kept short (typically 10-20 lines). Also make up a title for your thesis (note that this is not necessarily the title of the used literature or the title from our topic list). It is important to make your own reasoning about a title that describes the thesis best from your point of view.

**References**

Each thesis contains a reference list that contains at least the literature used in your thesis. In the digital libraries of DBLP, ACM, IEEE, or Springer you can find detailed literature reference information. For conferencing proceedings or journals ALWAYS specify the pages. For journals, additionally provide volume and journal number. Do not rely on the authors to do their references correct (e.g., reference list in a paper or at the author's website). Sometimes this references are wrong are incomplete. Also do not rely on search engines like CiteSeer or Google Scholar: always verify the correctness and completeness of your references. Especially, it is insufficient if you only provide links to the papers or citations in the web.

**Further Reading**

For further reading we advice

- Style - 10 Lessons in Clarity an Grace

University Library Signature: DLW1336 - Elements of Style

Free Online Version available here

University Library Signature: DLY1271 - Grammatically Correct

University Library Signature: ENI2642 - Three Sins of Authors in Computer Science and Math

# Submission of your Seminar Thesis

The thesis has to be created with LaTeX using our customized template, which you can download **here**, or you can clone the git-repository. We will create a complete volume consisting of all submissions.

You have to submit the LaTeX sources (your subfolder from the template is enough) AND a complete pdf of your seminar thesis by mail. The mail shall contain only one zip or tar.gz file with these data and must be sent to Sascha Brandt. Please do NOT include your matriculation number in your thesis.

For the LaTeX document you have to follow the following rules:

- Each author gets his own
**prefix**. (Example: the author "Matthias Fischer" gets his unique prefix "MaFi". Make sure there are no conflicts with other students.) - All your LaTeX files and pictures have to be contained in a single subfolder of the template using your
**prefix**as name. - There is only one "*.tex" file for your complete seminar thesis.
- The name of your LaTeX file consists only of your
**prefix**supplemented by the suffix ".tex" (e.g., "MaFi.tex"). - You can modify the "SI" folder and "SI.tex" in the template as a starting point.
- The document must be compiled with pdflatex. Hence, pictures must be included as pdf, jpg or png.
- To compile the document, you need to include your LaTeX file by adding the command "\includeseminar{...}" to the "main.tex" file in the root folder. (e.g., "\includeseminar{MaFi/MaFi}")
- Your file must be encoded in UTF-8.
- Your highest breakdown-level is \section. (Thus, you can use \section, \subsection, \subsubsection, \paragraph, etc.)
- To distinguish all self-defined commands, labels and references, each author gets his own prefix. (Example: the author "Matthias Fischer" gets his unique prefix "MaFi".)
- Each command, label and reference consists of the prefix, followed by an individual identifier. Thus, if Matthias wants to call a label "myCoolLabel", the label has to be defined by \label{MaFi:MyCoolLabel}.
- After the \maketitle call in your LaTeX document, you have to add your
**abstract**with the command "\abstract{ ... }". After the abstract add your local table of contents with the commands "\makeminitoc". - We only use the svmult
**theorem**environment. This means, the option "nospthms" and the package "amsthm" can not be used. (The package "amsthm" is not compatible to "svmult".) - We do not use the BibTeX compiler to process literature
**references**. Instead of this, you have to add your literature references like presented in the template file "SI.tex". You have to follow the style given in the template file, i.e., "author, title, year,...". - To format the
**pseudocode**of your algorithms you can either use "algorithmicx" together with its floating environment "algorithm" from the package "algorithms", or you can use the "listings" environment. We recommend to start with predefined commands as given by package "algpseudocode". We do not use the package "algorithmic". - You are not allowed to modify the "main.tex" file (apart from the \includeseminar command) or any other file in the root folder of the template. This also means, that you cannot use any other packages as specified in the main file.

# Topics

## Topic 1: Machine Minimization for Job Scheduling

In their paper [1], Chuzhoy et al. study a scheduling problem in which $n$ jobs characterized by release times, deadlines and arbitrary sizes need to be scheduled on a minimum number of machines such that all deadlines are met. They propose a polynomial-time algorithm which provides $O(\sqrt{\log n/ \log \log n})$-approximations and which is based on (randomized) rounding of an optimal (fractional) solution to a suitable linear program. It improves upon the previously best known $O(\log n/ \log \log n)$-approximation algorithm dated back to 1987 [2].

Link:[1] https://ieeexplore.ieee.org/abstract/document/1366227

Link:[2] https://link.springer.com/article/10.1007/BF02579324

Advisor: Simon Pukrop

## Topic 2: Scheduling Unrelated Parallel Machines - the (generalized) Assignment Problem

Consider the following scheduling problem. There are m parallel machines and n independent jobs. Each job is to be assigned to one of the machines. The processing of job j on machine i requires time p_ij. The objective is to find a schedule that minimizes the makespan.

In [1] the main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. They also present a polynomial approximation scheme for the case that the number of machines is fixed.

In contrast to our main result, they prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unless P = NP.

In [2] each job j on machine i incurs a cost of c_ij, each machine i is available for T_i time units, and the objective is to minimize the total cost incurred. The main result is as follows. There is a polynomial-time algorithm that, given a value C, either proves that no feasible schedule of cost C exists, or else finds a schedule of cost at most C where each machine i is used for at most 2 T_i time units.

Link:[1] https://link.springer.com/article/10.1007/BF01585745

Link:[2] https://link.springer.com/article/10.1007/BF01585178

Advisor: Simon Pukrop

## Topic 3: The Complexity of Scheduling Trees with Communication Delays

Consider the problem of finding a minimum-length schedule on m machines for a set of n unit-length tasks with a forest of intrees as precedence relation, and with unit interprocessor communication delays. First, they prove that this problem is NP-complete; second, they derive a linear time algorithm for the special case that m equals 2.

Link: www.sciencedirect.com/science/article/pii/S0196677496900073

Advisor: Simon Pukrop

## Topic 4: Scheduling to Minimize Max Flow Time: Off-line and On-line Algorithms

The author investigates the max flow time scheduling problem in the off-line and on-line setting. They prove positive and negative theoretical results. In the off-line setting, they address the unrelated parallel machines model and present the first known fully polynomial time approximation scheme, when the number of machines is fixed. In the on-line setting and when the machines are identical, they analyze the First In First Out (FIFO) heuristic when preemption is allowed. They show that FIFO is an on-line algorithm with a (3-2/m)-competitive ratio. Finally, they present two lower bounds on the competitive ratio of deterministic on-line algorithms.

Link: https://www.worldscientific.com/doi/abs/10.1142/S0129054104002480

Advisor: Simon Pukrop

## Topic 5: Local spreading algorithms for autonomous robot systems

This paper studies local algorithms for autonomous robot systems, namely, algorithms that use only information of the positions of a bounded number of their nearest neighbors. The paper focuses on the spreading problem. It defines measures for the quality of spreading, presents a local algorithm for the one-dimensional spreading problem, proves its convergence to the equally spaced configuration and discusses its convergence rate in the synchronous and semi-synchronous settings. It then presents a local algorithm achieving the exact equally spaced configuration in finite time in the synchronous setting, and proves it is time optimal for local algorithms. Finally, the paper also proposes a possible algorithm for the two-dimensional case and presents partial simulation results of its effectiveness.

Link: https://doi.org/10.1016/j.tcs.2008.02.007

Advisor: Jannik Castenow

## Topic 6: Autonomous mobile robots with lights

We consider the well known distributed setting of computational mobile entities, called robots, operating in the Euclidean plane in Look-Compute-Move (LCM) cycles. We investigate the computational impact of expanding the capabilities of the robots by endowing them with an externally visible memory register, called light, whose values, called colors, are persistent, that is they are not automatically reset at the end of each cycle. We refer to so endowed entities as luminous robots. We study the computational power of luminous robots with respect to the three main settings of activation and synchronization: fully-synchronous, semi-synchronous, and asynchronous. We establish several results. A main contribution is the constructive proof that asynchronous robots, illuminated with a constant number of colors, are strictly more powerful than traditional semi-synchronous robots. We also constructively prove that, for luminous robots, the difference between asynchrony and semi-synchrony disappears. This result must be contrasted with the strict dominance between the models without lights (even if the robots are enhanced with an unbounded amount of persistent internal memory). Additionally we show that there are problems that robots cannot solve without lights, even if they are fully-synchronous, but can be solved by asynchronous luminous robots with O (1) colors. It is still open whether or not asynchronous luminous robots with O (1) colors are more powerful than fully-synchronous robots without lights. We prove that this is indeed the case if the robots have the additional capability of remembering a single snapshot. This in turn shows that, for asynchronous robots, to have O(1) colors and a single snapshot renders them more powerful than to have an unlimited amount of persistent memory (including snapshots) but no lights.

Journal: https://doi.org/10.1016/j.tcs.2015.09.018

Paper: https://ieeexplore.ieee.org/document/6258023

Advisor: Jannik Castenow

## Topic 7: TuringMobile: A Turing Machine of Oblivious Mobile Robots with Limited Visibility and Its Applications

In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the snapshot to compute a destination point, and it moves toward its destination. Each robot is punctiform and memoryless, it operates in R^m, it has a local reference system independent of the other robots' ones, and is activated asynchronously by an adversarial scheduler. Moreover, the robots are non-rigid, in that they may be stopped by the scheduler at each move before reaching their destination (but are guaranteed to travel at least a fixed unknown distance before being stopped). We show that despite these strong limitations, it is possible to arrange 3m+3k of these weak entities in R^m to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with k registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number. We also prove that this task is impossible with fewer than three robots. Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation (of which Gathering is a special case) with limited visibility. Interestingly, our investigation implies that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient.

Paper: http://drops.dagstuhl.de/opus/volltexte/2018/9808/pdf/LIPIcs-DISC-2018-19.pdf

Full Version: https://arxiv.org/pdf/1709.08800.pdf

Advisor: Jannik Castenow

## Topic 8: Meeting in a Polygon by Anonymous Oblivious Robots

The Meeting problem for k ≥ 2 searchers in a polygon P (possibly with holes) consists in making the searchers move within P, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of P, we minimize the number of searchers k for which the Meeting problem is solvable. Specifically, if P has a rotational symmetry of order σ (where σ = 1 corresponds to no rotational symmetry), we prove that k = σ + 1 searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with k = 2 searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations (provided that the coordinates of the polygon’s vertices are algebraic real numbers in some global coordinate system), and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self- stabilizing map construction subroutine which is of independent interest.

Paper: https://doi.org/10.4230/LIPIcs.DISC.2017.14

Advisor: Jannik Castenow

## Topic 9: Online Problems and the Parking Permit Problem

Online algorithms deal with situations in which the future is unknown. Most examples of online algorithms consider purchases which remain forever. This may not always be the case in practice. For example, web servers, once purchased, are assumed to remain indefinitely for no extra charge. However, aside from its initial purchase price, a web server may also have a cost for power, internet connection, and occasional service. Motivated by this, purchases with time durations are considered and one of the first problems to consider these is the Parking Permit Problem. Suppose that I either walk or drive to work each day (depending on the weather). Every time I drive, I need a valid parking permit. Daily, weekly, monthly, and yearly permits are available with different costs (with longer duration permits tending to cost less per day). If I know I will drive each day then it would be most efficient to purchase the longest-duration permit, but since I drive only occasionally, determining which permit to buy requires predicting an unknown future.

The author of this paper gives deterministic and randomized approximation algorithms, which are nearly optimal, for the Parking Permit Problem.

The goal of this topic is to understand online algorithms which have time durations, using the example of the Parking Permit Problem. This can be an interesting study of online algorithms since almost any online problem can be seen from this perspective.

Paper: www.cs.ucla.edu/~awm/papers/parking.pdf

Advisor: Friedhelm Meyer auf der Heide

## Topic 10: Smoothed Analysis of Three Combinatorial Problems

Smoothed analysis combines elements over worst-case and average case analysis. For an instance x, the smoothed complexity is the average complexity of an instance obtained from x by a perturbation. The smoothed complexity of a problem is the worst smoothed complexity of any instance. Spielman and Teng introduced this notion for continuous problems. We apply the concept to combinatorial problems and study the smoothed complexity of three classical discrete problems: quicksort, left-to-right maxima counting, and shortest paths.

Paper: https://www.researchgate.net/publication/47841595_Smoothed_Analysis_of_Three_Combinatorial_Problems/link/02bfe50f90147dcaaf000000/download

Advisor: Friedhelm Meyer auf der Heide

## Topic 11: Novel architectures for Peer-to-Peer applications: The continuous-discrete approach

The task of a Peer-to-Peer Network is to maintain a network structure and functionality in a dynamic environment where the participants of the network change over time. They lack a central control, avoid a single-point-of-failure and scale well when the size of the network grows.

The authors propose a new approach the construction of Peer-to-Peer networks based on a dynamic decomposition of a continuous space into cells corresponding to peers. In fact, they propose a tool to transform a discrete graph definition to a continuous graph definition. In Peer-to-Peer networks, a continuous graph allows joining and leaving nodes in a simple way. They propose a continuous graph with constant degree and logarithmic routing performance by applying the continuous-discrete approach on the De Bruijn Graph.

Paper: https://dl.acm.org/citation.cfm?id=1273350

Advisor: Friedhelm Meyer auf der Heide

## Topic 12: All-pairs Min-cut tree

Let G=(V,E) be an undirected graph with positive capacity on each edge. There exists a tree T on V that stores min-cut between each pair of vertices: The value of min-cut between two vertices u and v in G is the weight of the least weight edge on the path between u and v in T. The tree T is thus called all-pairs cut-tree. Gomory and Hu presented the first algorithm to compute a cut-tree in 1961. Subsequently Gusfield presented simpler algorithm to compute cut-tree and flow-tree in 1990.

Paper by Gomory and Hu:

Gomory, R. E.; Hu, T. C. (1961). "Multi-terminal network flows". Journal of the Society for Industrial and Applied Mathematics. 9 (4): 551–570.

doi:10.1137/0109047

Paper by Dan Gusfield:

Dan Gusfield; Very Simple Methods for All Pairs Network Flow Analysis. SIAM J. Comput. 19(1): 143-155 (1990).

https://doi.org/10.1137/0219009

Advisor: Surender Baswana

## Topic 13: Fault-Tolerant subgraph for single source reachability

Let G=(V,E) be a directed graph on n vertices with a designated source vertex s. Let k be any given positive integer. The aim is to compute a sparse subgraph G’ of G such that for any set F of k failed vertices, the following assertion holds for each v\in V:

There is a path from s to v in G’ if and only if there is a path from s to v in G.

For k=1, there exists a simple algorithm for this problem based on DFS traversal. However, for any generic k, there exists an algorithm based on farthest min-cuts. The subgraph computed by this algorithm has O(n2^k) edges and this bound is asymptotically tight as well.

Surender Baswana, Keerti Choudhary, Liam Roditty:

Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal. SIAM J. Comput. 47(1): 80-95 (2018)

Advisor: Surender Baswana

## Topic 14: Approximate Distance oracles

Let G=(V,E) be an undirected graph with positive weights on edges. We can store all-pairs distances in a n by n matrix. This quadratic bound on the space is too large and impractical for most of the real world graphs which are of huge size. The aim is to build a compact data structure that takes sub-quadratic space and still can report approximate distance between any pair of vertices in O(1) time. This aim may look too ambitious. But, in a groundbreaking result, Thorup and Zwick showed that it is indeed possible. Moreover the trade-off between size of the data structure and the approximation factor is optimal assuming the famous girth conjecture of Erdos.

The paper is:

Mikkel Thorup, Uri Zwick: Approximate distance oracles. J. ACM 52(1): 1-24 (2005).

Advisor: Surender Baswana

## Topic 15: Lowest Common Ancestor (LCA) problem and Level Ancestor (LA) problem simplified.

Let T be a rooted tree on n vertices. For any two vertices u and v, LCA(u,v) is the nearest ancestor common to both i and j. The aim is to build an O(n) size data structure so that we can report LCA for any pair of vertices in O(1) time. Similar problem is Level Ancestor problem defined as follows - Build an O(n) size data structure that, for any vertex u and integer i, report the ancestor at distance i from u in O(1) time. Although originally there existed complex algorithms for these problems, new algorithms were devised that were drastically simple.

The papers are:

Michael A. Bender, Martin Farach-Colton: The LCA Problem Revisited. LATIN 2000: 88-94.

Michael A. Bender, Martin Farach-Colton:The Level Ancestor Problem simplified. Theor. Comput. Sci. 321(1): 5-12 (2004)

Advisor: Surender Baswana