1 citations · 1 across the 10 of their papers we have counts for
14 papers
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…
Faster Dynamic -Coloring Against Adaptive Adversaries
Maxime Flin, Magnús M. Halldórsson
We consider the problem of maintaining a proper -vertex coloring in a graph on -vertices and maximum degree undergoing edge insertions and deletions. We give a rando…
When MIS and Maximal Matching are Easy in the Congested Clique
Keren Censor-Hillel, Tomer Even, Maxime Flin +1
Two of the most fundamental distributed symmetry-breaking problems are that of finding a maximal independent set (MIS) and a maximal matching (MM) in a graph. It is a major open qu…
Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs
Maxime Flin, Magnús M. Halldórsson, Alexandre Nolin
Graph coloring is fundamental to distributed computing. We give the first general treatment of the coloring of virtual graphs, where the graph to be colored is locally embedded…
Decentralized Distributed Graph Coloring: Cluster Graphs
Maxime Flin, Magnus M. Halldorsson, Alexandre Nolin
Graph coloring is fundamental to distributed computing. We give the first sub-logarithmic distributed algorithm for coloring cluster graphs. These graphs are obtained from the unde…
Vertex Coloring in Communication
Maxime Flin, Parth Mittal
We study the communication complexity of vertex coloring, where the edges of an -vertex graph of maximum degree are partitioned between two players. We provide a ra…
Fast Coloring Despite Congested Relays
Maxime Flin, Magnús M. Halldórsson, Alexandre Nolin
We provide a -round randomized algorithm for distance-2 coloring in CONGEST with colors. For , this improves exponentially…
Coloring Fast with Broadcasts
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
We present an -round distributed algorithm for the -coloring problem, where each node broadcasts only one -bit message per round to its neighbors…
A Distributed Palette Sparsification Theorem
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
The celebrated palette sparsification result of [Assadi, Chen, and Khanna SODA'19] shows that to compute a coloring of the graph, where denotes the maximum degree, it suf…