3 citations · 8 across the 12 of their papers we have counts for
10 papers · 1 filter
Classification of Local Optimization Problems in Directed Cycles
Thomas Boudier, Fabian Kuhn, Augusto Modanese +2
We present a complete classification of the distributed computational complexity of local optimization problems in directed cycles for both the deterministic and the randomized LOC…
Is a LOCAL algorithm computable?
Antonio Cruciani, Avinandan Das, Massimo Equi +4
Common definitions of the "standard" LOCAL model tend to be sloppy and even self-contradictory on one point: do the nodes update their state using an arbitrary function or a comput…
Orientation does not help with 3-coloring a grid in online-LOCAL
Thomas Boudier, Filippo Casagrande, Avinandan Das +4
The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know o…
New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
Alkida Balliu, Corinna Coupette, Antonio Cruciani +6
In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing. First, we show that there is no d…
Strong and Hiding Distributed Certification of Bipartiteness
Benjamin Jauregui, Augusto Modanese, Pedro Montealegre +1
In this paper, we study the problem of certifying whether a graph is bipartite (i.e. -colorable) with a locally checkable proof (LCP) that is able to hide a -coloring from th…
Distributed Quantum Advantage for Local Problems
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy +10
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 prio…