3 papers
cs.DC2026
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…
cs.DC2025
Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure
Pierre Fraigniaud, Minh Hang Nguyen, Ami Paz
Consensus is arguably the most studied problem in distributed computing as a whole, and particularly in the distributed message-passing setting. In this latter framework, research…
cs.DS2024
Distributed Model Checking on Graphs of Bounded Treedepth
Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre +2
We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the CONGEST model. To our knowl…