Joel Rybicki's MSc thesis "Exact bounds for distributed graph colouring" was graded with laudatur, the highest grade available. Only top 1% of all MSc thesis at the Department of Computer Science have been awarded this grade, so the thesis must be exceptionally good.

What does a thesis worth laudatur look like? Below, Joel will describe the topic and contents of the thesis, and then his supervisors will tell why it is so great.

Joel:

The thesis studies the computational complexity of the distributed graph colouring problem. In distributed computing, The structure of a distributed system is often modelled as a graph where the nodes represent processors and edges denote communication links between the processors. Many algorithmic problems in distributed computing relate to the structure of the communication graph.

The task in the graph colouring problem is to assign a colour to each node in the graph such that nodes connected by an edge have different colours. The colours are usually represented as integers and it is often desirable to use as few colours as possible. The problem is known to be hard: it is NP-complete to decide whether a graph can be coloured with at most k colours.

One way to measure the computational complexity of distributed problems is to study the amount of communication required to solve the problem. That is, how much information does a processor need to collect from nearby processors in order to compute the output? The thesis studies the complexity of colouring directed cycles and trees with at most three colours.

The main result improves the known upper and lower bounds for the complexity of 3-colouring directed cycles and trees. The new bounds are derived using computational analysis, as the existence of distributed colouring algorithms corresponds to the colourability of so-called neighbourhood graphs. Therefore, it is possible to find new distributed algorithms, or prove the non-existence of distributed colouring algorithms by solving combinatorial problems.

The computational tasks were solved with Boolean satisfiability (SAT) solvers (http://en.wikipedia.org/wiki/Boolean_satisfiability_problem) on the Ukko cluster. In addition, it thesis investigates how similar computational methods can be applied in studying the complexity of other distributed graph problems, such as maximal matchings.

Supervisors Jukka Suomela ja Petteri Kaski:

Joel Rybicki's MSc thesis "Exact bounds for distributed graph colouring" is an outstanding work in many ways. Rybicki obtains novel scientific results that are related to the foundations of distributed computing. The thesis is carefully written; it demonstrates extensive knowledge of the field of distributed algorithms, as well as proficiency in the versatile research methods of the field.

In the study of theoretical computer science, the design of new algorithms and the analysis of computational complexity has traditionally been manual work. In the discovery of mathematical proofs, Rybicki's thesis supplements the traditional techniques with computer-aided methods. The department's new high-performance cluster Ukko [1] has provided the extensive computing resources needed to carry out this kind of research.

Joel Rybicki is currently working as a research assistant in the research group "New Paradigms in Computing", which is led by Professor Petteri Kaski. One of the research themes of the group focuses on distributed algorithms, and more specifically on so-called local algorithms [3]. In this research area, a key objective is to understand which computational tasks related to computer networks can be solved efficiently. Joel Rybicki's work has established exact bounds on how efficiently we can solve tasks that are related to the coordination of a computer network, and the same techniques have a potential for a wider applicability in this research area as well.

[1] http://www.cs.helsinki.fi/en/compfac/high-performance-cluster-ukko

[2] http://www.cs.helsinki.fi/group/parac/

[3] http://www.cs.helsinki.fi/u/josuomel/local-survey 

Text: Hannu Toivonen
Graphics: Joel Rybicki
Photo: Tuomas Puikkonen