1 citations · 1 across the 10 of their papers we have counts for
6 papers · 1 filter
LOCAL LLL in Rounds
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
We provide a -round randomized LOCAL algorithm for the constructive Lovász Local Lemma with polynomial criterion , for a sufficiently l…
Quantum Advantage for Distributed Symmetry Breaking
Maxime Flin, Longcheng Li, Jukka Suomela
We present a distributed quantum algorithm that -colors cycles in rounds, with high probability. It follows that all locally checkable labeling problems (LCLs) that have…
Distributed Quantum Algorithms Cannot Color Cycles with Probability 1
Xavier Coiteux-Roy, Maxime Flin, Carlos de Gois +3
We prove that any distributed quantum algorithm that finds a -coloring with probability in a cycle of anonymous identical computers has to be global, that is, it needs $Ω(n)…
Beyond Brooks: -Coloring in Semi-Streaming
Maxime Flin, Magnús M. Halldórsson
Reed [J.~Comb.~Theory B, 1999] showed that graphs of maximum degree without -cliques are -colorable. We design a one-pass semi-streaming algorithm for com…
Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
Maxime Flin, Magnús M. Halldórsson, Manuel Jakob +1
For any , let be the maximum integer such that . We give a distributed \LOCAL algorithm that, given an integer , computes a valid -color…
2-Coloring Cycles in One Round
Maxime Flin, Alesya Raevskaya, Ronja Stimpert +2
We show that there is a one-round randomized distributed algorithm that can 2-color cycles such that the expected fraction of monochromatic edges is less than 0.24118. We also show…