5 papers
No Distributed Quantum Advantage for 3-Coloring Rooted Trees and 2-Coloring Even Cycles
Pierre Fraigniaud, Frédéric Magniez, Isabella Ziccardi
Significant effort has been devoted over the past decade to understanding whether quantum resources can provide advantages in distributed computing, and in particular whether they…
Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan
We present new distributed quantum algorithms for fundamental distributed computing problems, namely, leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Sea…
Quantum property testing in sparse directed graphs
Simon Apers, Frédéric Magniez, Sayantan Sen +1
We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the out…
Deterministic Even-Cycle Detection in Broadcast CONGEST
Pierre Fraigniaud, Maël Luce, Frédéric Magniez +1
We show that, for every , -freeness can be decided in rounds in the Broadcast CONGEST model, by a deterministic algorithm. This (deterministic) roun…
Quantum Communication Advantage for Leader Election and Agreement
Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan
This work focuses on understanding the quantum message complexity of two central problems in distributed computing, namely, leader election and agreement in synchronous message-pas…