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.

Conference Articles

2023Locality in online, dynamic, sequential, and distributed graph algorithmsICALP 2023

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 presents the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each node we get to see its radius-TT 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-TT neighborhood, the SLOCAL model, which is the sequential counterpart of LOCAL, and the dynamic-LOCAL model, where changes in the dynamic input graph only influence the radius-TT neighborhood of the point of change.

The SLOCAL and dynamic-LOCAL models are sandwiched between the LOCAL and online-LOCAL models. In general, all four models are distinct, but we study in particular locally checkable labeling problems (LCLs), which is a family of graph problems extensively studied in the context of distributed graph algorithms. We prove 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)O(\log^* n), Θ(log⁡n)\Theta(\log n), or nΘ(1)n^{\Theta(1)} - in all four models. In particular, this result enables one to generalize prior lower-bound results from the LOCAL model to all four models, and it also allows one to simulate e.g. dynamic-LOCAL algorithms efficiently in the LOCAL model.

We also show that this equivalence does not hold in two-dimensional grids or general bipartite graphs. We provide an online-LOCAL algorithm with locality O(log⁡n)O(\log n) for the 3-coloring problem in bipartite graphs - this is a problem with locality Ω(n1/2)\Omega(n^{1/2}) in the LOCAL model and Ω(n1/10)\Omega(n^{1/10}) in the SLOCAL model.

2023Sinkless Orientation Made SimpleSOSA 2023

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 Ω(log⁡n)\Omega(\log n) in the deterministic LOCAL model and O(log⁡log⁡n)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.

To Appear

2023Brief Announcement: Distributed derandomization revisitedDISC 2023

We give a new, simple proof for the classic distributed derandomization result by Chang, Kopelowitz, and Pettie, and improve the result by reducing the needed assumptions on the type of randomness used.

One of the cornerstones of the distributed complexity theory is the derandomization result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves a locally checkable labeling problem (LCL) can be derandomized with at most exponential overhead. The original proof assumes that the number of random bits is bounded by some function of the input size. We give a new, simple proof that does not make any such assumptions—it holds even if the randomized algorithm uses infinitely many bits. While at it, we also broaden the scope of the result so that it is directly applicable far beyond LCL problems.

Manuscripts

2023No distributed quantum advantage for approximate graph coloring

We give an almost complete characterization of the hardness of cc-coloring χ\chi-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage.

To do that:

  1. We give a new distributed algorithm that finds a cc-coloring in χ\chi-chromatic graphs in O~(n1α)\tilde{\mathcal{O}}(n^{\frac{1}{\alpha}}) rounds, with α=⌈c−1χ−1⌉\alpha = \bigl\lceil\frac{c-1}{\chi - 1}\bigr\rceil.
  2. We prove that any distributed algorithm for this problem requires Ω(n1α)\Omega(n^{\frac{1}{\alpha}}) rounds.

Our upper bound holds in the classical, deterministic LOCAL model, while the near-matching lower bound holds in the non-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic LOCAL and randomized LOCAL but also quantum-LOCAL, even with a pre-shared quantum state.

We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or cc-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.

Thesis

2022Master's Thesis: Locally Checkable Labeling Problems in Rooted Trees in the Online-LOCAL Model of Computation

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 conference article.

2020Bachelor's Thesis: Temperature Measurement Using a Transmon Device

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.