# Henrik Lievonen

I am a doctoral researcher 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

- 2024No distributed quantum advantage for approximate graph coloring STOC 2024
We give an almost complete characterization of the hardness of $c$-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:

- We give a new distributed algorithm that finds a $c$-coloring in $\chi$-chromatic graphs in $\tilde{\mathcal{O}}(n^{\frac{1}{\alpha}})$ rounds, with $\alpha = \bigl\lceil\frac{c-1}{\chi - 1}\bigr\rceil$.
- We prove that any distributed algorithm for this problem requires $\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 $c$-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.

- 2024Distributed Binary Labeling Problems in High-Degree Graphs SIROCCO 2024
In this work we study the complexity of binary labeling problems as a function of all three parameters: $n$, $d$, and $\delta$. To this end, we introduce the family of

*structurally simple*problems, which includes, among others, all binary labeling problems in which cardinality constraints can be represented with a context-free grammar. We classify possible complexities of structurally simple problems. As our main result, we show that if the complexity of a problem falls in the broad class of $\Theta_{d,\delta}(\log n)$, then the complexity for each $d$ and $\delta$ is always either $\Theta(\log_d n)$, $\Theta(\log_\delta n)$, or $\Theta(\log n)$.Balliu et al. (DISC 2020) classified the hardness of solving

*binary labeling problems*with distributed graph algorithms; in these problems the task is to select a subset of edges in a 2-colored tree in which white nodes of degree $d$ and black nodes of degree $\delta$ have constraints on the number of selected incident edges. They showed that the deterministic round complexity of any such problem is $O_{d,\delta}(1)$, $\Theta_{d,\delta}(\log n)$, or $\Theta_{d,\delta}(n)$, or the problem is unsolvable. However, their classification only addresses complexity as a function of $n$; here $O_{d,\delta}$ hides constants that may depend on parameters $d$ and $\delta$.To prove our upper bounds, we introduce a new, more aggressive version of the

*rake-and-compress technique*that benefits from high-degree nodes.- 2023Brief Announcement: Distributed derandomization revisited DISC 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.

- 2023Locality in online, dynamic, sequential, and distributed graph algorithms ICALP 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-$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, 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-$T$ 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)$, $\Theta(\log n)$, or $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)$ for the 3-coloring problem in bipartite graphs - this is a problem with locality $\Omega(n^{1/2})$ in the LOCAL model and $\Omega(n^{1/10})$ in the SLOCAL model.

- 2023Sinkless Orientation Made Simple SOSA 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 $\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.

## Manuscripts

- 2024Local problems in trees across a wide range of distributed models
We classify Locally Checkable Labeling problems in a wide variety of distributed models of computation. In particular, we classify many problems in rooted and unrooted regular trees.

The

*randomized online-LOCAL*model captures a number of models of computing; it is at least as strong as all of these models:- the classical LOCAL model of distributed graph algorithms,
- the quantum version of the LOCAL model,
- finitely dependent distributions [e.g. Holroyd 2016],
- any model that does not violate physical causality [Gavoille, Kosowski, Markiewicz, DICS 2009],
- the SLOCAL model [Ghaffari, Kuhn, Maus, STOC 2017], and
- the dynamic-LOCAL and online-LOCAL models [Akbari et al., ICALP 2023].

In general, the online-LOCAL model can be much stronger than the LOCAL model. For example, there are

*locally checkable labeling problems*(LCLs) that can be solved with logarithmic locality in the online-LOCAL model but that require polynomial locality in the LOCAL model.However, in this work we show that in

*trees*, many classes of LCL problems have the same locality in deterministic LOCAL and randomized online-LOCAL (and as a corollary across all the above-mentioned models). In particular, these classes of problems do not admit any distributed quantum advantage.We present a near-complete classification for the case of

*rooted regular trees*. We also fully classify the super-logarithmic region in*unrooted regular trees*. Finally, we show that in general trees (rooted or unrooted, possibly irregular, possibly with input labels) problems that are global in deterministic LOCAL remain global also in the randomized online-LOCAL model.- 2024Online Locality Meets Distributed Quantum Computing
We extend the theory of locally checkable labeling problems (LCLs) from the classical LOCAL model to a number of other models that have been studied recently, including the quantum-LOCAL model, finitely-dependent processes, non-signaling model, dynamic-LOCAL model, and online-LOCAL model [e.g. STOC 2024, ICALP 2023].

First, we demonstrate the advantage that finitely-dependent processes have over the classical LOCAL model. We show that all LCL problems solvable with locality $O(\log^* n)$ in the LOCAL model admit a finitely-dependent distribution (with constant locality). In particular, this gives a finitely-dependent coloring for regular trees, answering an open question by Holroyd [2023]. This also introduces a new formal barrier for understanding the distributed quantum advantage: it is not possible to exclude quantum advantage for any LCL in the $\Theta(\log^* n)$ complexity class by using non-signaling arguments.

Second, we put limits on the capabilities of all of these models. To this end, we introduce a model called randomized online-LOCAL, which is strong enough to simulate e.g. SLOCAL and dynamic-LOCAL, and we show that it is also strong enough to simulate any non-signaling distribution and hence any quantum-LOCAL algorithm. We prove the following result for rooted trees: if we can solve an LCL problem with locality $o(\log\log n)$ in the randomized online-LOCAL model, we can solve it with locality $O(\log^* n)$ in the classical deterministic LOCAL model.

Put together, these results show that in trees the set of LCLs that can be solved with locality $O(\log^* n)$ is the same across all these models: locality $O(\log^* n)$ in quantum-LOCAL, non-signaling model, dynamic-LOCAL, or online-LOCAL is not stronger than locality $O(\log^* n)$ in the classical deterministic LOCAL model.

## 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.