Public defence, Computer Science, MSc (Tech) Henrik Lievonen

Title of the thesis: Locality in distributed quantum and online graph algorithms

Thesis defender: Henrik Lievonen
Opponent: Professor Artur Czumaj, Department of Computer Science, University of Warwick, United Kingdom 
Custos: Associate Professor Jukka Suomela, Aalto University School of Science

With the recent advances in computer science, the number of computers has grown exponentially, and at the same time, the need to connect them to solve ever larger problems has also increased. These types of computer networks are called distributed systems, and computations done on them are referred to as  distributed computing. This dissertation examines the locality of solving tasks in various models of distributed computing. Here locality means the distance information needs to travel in the network for the completion of a task. Because information traversal takes time, lower locality directly implies faster execution of tasks. This dissertation concerns itself with studying the locality of locally-checkable labeling problems; these are problems – or tasks – whose solution can be verified locally, but for which finding a solution may require transmitting information over long distances.

In this dissertation, locality is examined both through individual computational problems and by proving broad connections between many models of computation, which enables many results on the locality of problems to be extended to these models of distributed computing. Towards that end, this dissertation presents the first locally-checkable computational problem for which distributed quantum advantage can be proven: the problem in question can provably be solved faster in networks that have access to quantum computing than in fully-classical distributed systems. This problem is constructed by connecting many quantum games together; quantum games are simple mathematical co-operative games which can only be won with the help of quantum computers.

The second major contribution of this dissertation is to introduce locality into online graph algorithms. These are algorithms which process a network one node at a time, and after each node, they need to produce an output for that node such that, at the end, the produced solution is globally correct for the whole network. In general, it is known that many problems are impossible to solve in this model of computation unless the algorithm is given advice about the structure of the input network. This dissertation studies which problems are possible to be solved when the advice consists of the local structure of the network around the node, that is, all nodes and connections up to a given distance – this distance corresponds to locality. The dissertation shows that all problems solvable efficiently in either classical distributed systems or in distributed quantum systems can also be solved within this model using low locality. The dissertation also provides a new, fast algorithm for 3-coloring a network in this model, and shows that this algorithm is optimal.

Key words: distributed graph algorithms, distributed quantum algorithms, LCL problems

Thesis available for public display 7 days prior to the defence at Aalto University's public display page. 

Contact:
https://henriklievonen.fi/ 
https://research.cs.aalto.fi/da/