Henrik Lievonen

I am a PhD student at the Distributed Algorithms group at Aalto University. I started in early 2022, after finishing my Master's thesis. I work on understanding connections between distributed algorithms and other fields of mathematics and computer science.

In addition to research, I am the main developer for the automated grading system that is used at the highly-popular Programming Parallel Computers course. I also work as a teaching assistant on the course. I have contributed to the competitive programming grading system CSES.

Manuscripts

2022: Sinkless Orientation Made Simple arXiv

We provide new, simple proofs showing that the sinkless orientation problem separates the deterministic LOCAL and SLOCAL models.

The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is \(\Omega(\log n)\) in the deterministic LOCAL model and \(O(\log \log n)\) in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.

2022: Online Algorithms with Lookaround arXiv Poster

In this work, we give a unifying view of locality in four settings: distributed algorithms, sequential greedy algorithms, dynamic algorithms, and online algorithms.

We introduce a new model of computing, called the online-LOCAL model: the adversary reveals the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each new node the algorithm can also inspect its radius-\(T\) neighborhood before choosing the output. Instead of looking ahead in time, we have the power of looking around in space.

We compare the online-LOCAL model with three other models: the LOCAL model of distributed computing, where each node produces its output based on its radius-\(T\) neighborhood, its sequential counterpart SLOCAL, and the dynamic-LOCAL model, where changes in the dynamic input graph only influence the radius-\(T\) neighborhood of the point of change.

SLOCAL and dynamic-LOCAL models are sandwiched between LOCAL and online-LOCAL models, with LOCAL being the weakest and online-LOCAL the strongest model. In this work, we seek to answer the following question: is the online-LOCAL model strictly stronger than the LOCAL model when we look at graph algorithms for solving locally checkable labeling problems (LCLs)?

First, we show that for LCL problems in paths, cycles, and rooted trees, all four models are roughly equivalent: the locality of any LCL problem falls in the same broad class—\(O(\log^∗ n)\), \(\Theta(\log n)\), or \(n^{\Theta(1)}\)—in all four models. In particular, prior work on the LOCAL model directly generalizes to all four models.

Second, we show that this equivalence does not hold in two-dimensional grids. We show that the locality of the 3-coloring problem is \(O(\log n)\) in the online-LOCAL model, while it is known to be \(\Omega(\sqrt{n})\) in the LOCAL model.

Master's Thesis

2022: Locally Checkable Labeling Problems in Rooted Trees in the Online-LOCAL Model of Computation PDF Aaltodoc Slides

I introduce the online-LOCAL model, which combines online graph algorithms with the LOCAL model of distributed computation. I show that the online-LOCAL model is no more powerful than the LOCAL model when considering Locally Checkable Labeling problems in rooted trees.

There are many ways to classify algorithms. Online algorithms, for example, are algorithms that have to be able to handle input one element at a time. Offline algorithms, on the other hand, have access to the whole input. In the case of online graph algorithms, the structure of the underlying graph is fixed. The graph is revealed to the algorithm one node at a time. When a node is revealed, the algorithm has to decide its output for that node, and it cannot change its decision later.

Another way to classify algorithms is to divide them into centralized and distributed algorithms. In the case of graph algorithms, a centralized algorithm is a completely separate entity from the graph. When the nodes (or edges) of the graph are active parties in the execution of the algorithm, the algorithm is called a distributed algorithm. One commonly used model of distributed computation is the LOCAL model. In the LOCAL model, all nodes are computing their own part of the result in parallel. The nodes only see their own local neighborhood and need to base their decision only on this local view.

In this thesis, I introduce the online-LOCAL model, which combines the power of online graph algorithms and LOCAL algorithms. Like online graph algorithms, online-LOCAL algorithms need to react to nodes being revealed one at a time. Unlike online graph algorithms, online-LOCAL algorithms also get to see the local neighborhood around the nodes before needing to make their decisions.

The online-LOCAL model is a very strong model of computation. In general, there are problems that are trivial in the online-LOCAL model, but difficult to solve with online graph algorithms and LOCAL algorithms. In this thesis, I restrict my attention to the class of problems known as locally checkable labeling problems. These are a broad class of problems for which a solution is valid if it looks valid in all local neighborhoods. In particular, I show that for locally checkable labeling problems in rooted regular trees, the online-LOCAL model is approximately as powerful as the LOCAL model.

The thesis worked as inspiration for related manuscript.

Bachelor's Thesis

2020: Temperature Measurement Using a Transmon Device PDF

Henrik Lievonen
Supervisor: Sorin Paraoanu
Advisor: Andrey Lebedev

I analyze the data from a quantum mechanical transmon device to determine the temperature of the sample. The developed thermometer works for temperatures in the range of tens to hundreds of millikelvins.

I have developed a method for measuring temperature in range of tens to hundreds of millikelvins. The method uses a quantum mechanical tarnsmon device as the thermometer. The method is based on the fact that at the thermodynamical equilibrium the state of a quantum mechanical system is distributed according to the Boltzmann distribution. By fitting the Boltzmann distribution to the measured state distribution, one can determine the temperature of the system.

The state distribution of the system is measured by applying a measurement pulse and measuring the reflected pulse. The measurement pulse collapses the quantum mechanical state to one of the eigenstates of the Hamiltonian of the system. The energy level of the eigenstate determines the properties of the reflected measurement pulse.

In practice the measured pulse is very weak and noisy. To improve the signal-to-noise ratio, the measurement is repeated multiple times and the response signals are averaged. Each state of the system produces a different reflected pulse, and averaging multiple measurements loses the information of the distribution of those pulses and, by proxy, the states. To recover the information of the state distribution, the system is prepared in different states before the measurement. Because we know how the preparation affects the state, we can solve the state distribution from this set of measurements. We can then use the Boltzmann distribution to solve for the temperature of the sample.

The method has been developed using a transmon qutrit, but it works also for other kinds of quantum mechanical systems. The method produces plausible results for the temperatures, but not all sources of errors could be determined. More measurements are needed to unravel these error sources.