Aalto computer scientists in STOC 2025

News

Aalto computer scientists in STOC 2025

Published: 19.6.2025

This year two papers from Aalto Department of Computer Science were accepted to the Symposium on Theory of Computing (STOC).

Artistic illustration: Algorithms over a computer chip

The 57th ACM Symposium on Theory of Computing (STOC 2025) is sponsored by the ACM Special Interest Group on Algorithms and Computation Theory. STOC 2025 is held in Prague, Czech Republic on 23-27 June, 2025.

Accepted papers 2025

In alphabetical order. Click the title to see the authors and the abstract.

Authors

Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, and Isadora Veeren

Abstract

We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prior work, such a separation was known only for an artificial graph problem with an inherently global definition [Le Gall et al. 2019]. We present a problem that we call iterated GHZ, which is defined using only local constraints. Formally, it is a family of locally checkable labeling problems [Naor and Stockmeyer 1995]; in particular, solutions can be verified with a constant-round distributed algorithm. We show that in graphs of maximum degree Δ, any classical (deterministic or randomized) LOCAL model algorithm will require Ω(Δ) rounds to solve the iterated GHZ problem, while the problem can be solved in 1 round in quantum-LOCAL. We use the round elimination technique to prove that the iterated GHZ problem requires Ω(Δ) rounds for classical algorithms. This is the first work that shows that round elimination is indeed able to separate the two models, and this also demonstrates that round elimination cannot be used to prove lower bounds for quantum-LOCAL. To apply round elimination, we introduce a new technique that allows us to discover appropriate problem relaxations in a mechanical way; it turns out that this new technique extends beyond the scope of the iterated GHZ problem and can be used to e.g. reproduce prior results on maximal matchings [FOCS 2019, PODC 2020] in a systematic manner.

Authors

Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhoň, and Jukka Suomela

Abstract

We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-signaling distributions [e.g. STOC 2024], B. finitely-dependent processes [e.g. Forum Math. Pi 2016], and C. locality in online graph algorithms and dynamic graph algorithms [e.g. ICALP 2023]. We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the randomized online-LOCAL model. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds. Our main technical results are these: 1. All LCL problems solvable with locality O(log⋆n) in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality O(1). This answers an open question by Holroyd [2024], and also presents a new barrier for proving bounds on distributed quantum advantage using causality-based arguments. 2. In rooted trees, if we can solve an LCL problem with locality o(logloglogn) in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality O(log⋆n) in the classical deterministic LOCAL model. One of many implications is that in rooted trees, O(log⋆n) locality in quantum-LOCAL is not stronger than O(log⋆n) locality in classical LOCAL.

Accepted papers 2024

STOC 2024 was held in Vancouver, Canada on 24-28 June, 2024.

Authors

Andreas Björklund (IT University of Copenhagen); Petteri Kaski (911��)

Abstract

Strassen's asymptotic rank conjecture [{\em Progr.~Math.}~120~(1994)] claims a strong submultiplicative upper bound on the rank of a three-tensor obtained as an iterated Kronecker product of a constant-size base tensor. The conjecture, if true, most notably would put square matrix multiplication in quadratic time. We note here that some more-or-less unexpected algorithmic results in the area of exponential-time algorithms would also follow. Specifically, we study the so-called set cover conjecture, which states that for any $\epsilon>0$ there exists a positive integer constant $k$ such that no algorithm solves the $k$-Set Cover problem in worst-case time $\bO((2-\epsilon)^n|\mathcal F|\operatorname{poly}(n))$. The $k$-Set Cover problem asks, given as input an $n$-element universe $U$, a family $\mathcal F$ of size-at-most-$k$ subsets of $U$, and a positive integer $t$, whether there is a subfamily of at most $t$ sets in $\mathcal F$ whose union is $U$. The conjecture was formulated by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh~in the monograph {\em Parameterized Algorithms} [Springer,~2015], but was implicit as a hypothesis already in Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, and Wahlstr{\"{o}}m~[CCC~2012, {\em ACM~Trans.~Algorithms}~2016], there conjectured to follow from the Strong Exponential Time Hypothesis. We prove that if the asymptotic rank conjecture is true, then the set cover conjecture is false. Using a reduction by Krauthgamer and Trabelsi [STACS~2019], in this scenario we would also get an $\bO((2-\delta)^n)$-time randomized algorithm for some constant $\delta>0$ for another well-studied problem for which no such algorithm is known, namely that of deciding whether a given $n$-vertex directed graph has a Hamiltonian cycle.

Authors

Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, Jukka Suomela

Abstract

We give an almost complete characterization of the hardness of c-coloring χ-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 c-coloring in χ-chromatic graphs in ̃(n1α) rounds, with α=⌊c−1χ−1⌋. 2) We prove that any distributed algorithm for this problem requires Ω(n1α) 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.