Public defence in Computer Science, M.Sc. Jan Studený

Title of the thesis: Designing and finding very fast distributed algorithms for bounded-degree graphs

Doctoral student: Jan Studený
Opponent: Associate Professor Seth Gilbert, National University of Singapore, Singapore
Custos: Associate Professor Jukka Suomela, Aalto University School of Science, Department of Computer Science

Distributed computing studies models where computation is split between multiple interconnected entities which can communicate with each other to achieve a common goal. In this thesis we look at the setting where the communication network is sparse, meaning it has a bounded degree.

We first study a family of problems where solutions can be locally checked, known as locally checkable labeling (LCL) problems. This rich family contains, for example, the problems of computing proper colorings, maximal independent set, maximal matching and orientation problems. The aim is to completely characterize these LCL problems in a given network topology and automatically synthesize an asymptotically optimal algorithm. We have achieved a complete characterization and synthesis for the following graph families: paths, cycles and regular rooted trees and a partial characterization for regular undirected trees. The results are complemented by unified implementations of all classifiers for asymptotic round complexity. Some of the results are using a newly discovered connection to automata theory while others use a novel concept of certificates of solvability. In the second part of the thesis we focus on sparse matrix multiplication in a setting of low-bandwidth communication. We show that in the case of uniformly sparse matrices with at most d non-zeroes per row and column we can break the quadratic barrier with respect to d and obtain a faster algorithm. One of the techniques used is to iteratively find regions that are locally dense and use more efficient dense multiplication algorithms for computing those parts.

The study contributes to theoretical understanding of sparse distributed computing systems, enriching ongoing work in graph theory, automata theory, and computational optimization. The results demonstrate that fully characterizing LCL problems for specific graph topologies is viable, and the techniques for sparse matrix multiplication show that it is possible to enhance performance in communication-constrained environments. The findings are applicable in distributed systems where communication networks have a sparse structure, such as sensor networks, peer-to-peer systems, and communication-efficient parallel computing. The sparse matrix multiplication results are relevant to fields that rely on large-scale data processing with sparse data structures.

Key words: distributed algorithms, locally checkable labeling, matrix multiplication, locality, distributed computational complexity, algorithm synthesis, congested clique, low-bandwidth model

Thesis available for public display 10 days prior to the defence at: https://aaltodoc.aalto.fi/doc_public/eonly/riiputus/ 

Contact information:

Doctoral theses of the School of Science: https://aaltodoc.aalto.fi/handle/123456789/52