Arrow Research search

Author name cluster

Henrik Lievonen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers
1 author row

Possible papers

3

STOC Conference 2025 Conference Paper

Online Locality Meets Distributed Quantum Computing

  • Amirreza Akbari
  • Xavier Coiteux-Roy
  • Francesco d'Amore 0001
  • François Le Gall
  • Henrik Lievonen
  • Darya Melnyk
  • Augusto Modanese
  • Shreyas Pai

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 (logloglog n ) 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.

Details