Arrow Research search

Author name cluster

Xavier Coiteux-Roy

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.

4 papers
2 author rows

Possible papers

4

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

TCS Journal 2024 Journal Article

On computable numbers, with an application to the Druckproblem

  • Sophie Berthelette
  • Gilles Brassard
  • Xavier Coiteux-Roy

In the famous paper in which he introduced what is now known as the Turing machine, Alan Turing gave a definition of computable real numbers under which it turns out that multiplication by 3 is uncomputable. This shortcoming vanished in a Correction to his paper that Turing himself published shortly afterwards, but it clearly illustrates the subtlety of defining computability issues correctly. In this paper, we give the name “printable” to real numbers that Turing originally called “computable”, we recall what is now the generally accepted definition of computable real numbers (which is not quite Turing's amended definition, but is equivalent to it), and we contrast the two notions. Despite the fact that the multiplication by 3 of printable numbers is uncomputable, as opposed to the same operation on computable numbers, a real number is computable if and only if it is printable. The resolution of this apparent paradox is that no machine can transform the “computable” description of a real number to its “printable” description, as Turing proved in his Correction. Finally, we address the subtle issue of allowing or not the printable description of a real number to end with an infinite sequence of 9s (or of 1s in binary), which was left open by Turing in his Correction. Several of these results were already known, as they appear in scattered places, some in non-refereed publications, but we give a unified treatment with some different proofs and a historical perspective.

Details DOI
v2026.09.13