5 citations · 23 across the 20 of their papers we have counts for
28 papers
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…
What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
Lélia Blin, Fedor V. Fomin, Pierre Fraigniaud +5
The question of 'what can be computed locally?' lies at the heart of distributed computing in networks. As established in Naor and Stockmeyer's seminal paper (STOC 1993), this ques…
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…
Even-Cycle Detection in the Randomized and Quantum CONGEST Model
Pierre Fraigniaud, Mael Luce, Frederic Magniez +1
We show that, for every , -freeness can be decided in rounds in the \CONGEST{} model by a randomized Monte-Carlo distributed algorithm with one-side…
Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing
Arthur Braida, Simon Martiel, Ioan Todinca
Quantum annealing (QA) holds promise for optimization problems in quantum computing, especially for combinatorial optimization. This analog framework attracts attention for its pot…
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…