39 citations · 155 across the 35 of their papers we have counts for
52 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…
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…
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…
The Computational Power of Distributed Shared-Memory Models with Bounded-Size Registers
Carole Delporte, Hugues Fauconnier, Pierre Fraigniaud +2
The celebrated Asynchronous Computability Theorem of Herlihy and Shavit (STOC 1993 and STOC 1994) provided a topological characterization of the tasks that are solvable in a distri…
One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks
Hagit Attiya, Pierre Fraigniaud, Ami Paz +1
The paper compares two generic techniques for deriving lower bounds and impossibility results in distributed computing. First, we prove a speedup theorem (a-la Brandt, 2019), for w…
Distributed Certification for Classes of Dense Graphs
Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre +2
A proof-labeling scheme (PLS) for a boolean predicate on labeled graphs is a mechanism used for certifying the legality with respect to of global network states in a distri…