Maxime Flin

activity

20232026

most citedSublogarithmic Distributed Vertex Coloring with Optimal Number of Colors

1 citations · 1 across the 10 of their papers we have counts for

collaborators

Showing 2026 · cs.DSShow all

4 papers · 2 filters

cs.DS2026

LOCAL LLL in $poly (lo g lo g n)$ Rounds

Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2

We provide a $poly (lo g lo g n)$ -round randomized LOCAL algorithm for the constructive Lovász Local Lemma with polynomial criterion $p d^{c} < 1$ , for a sufficiently l…

cs.DS2026

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 $3$ -coloring with probability $1$ in a cycle of anonymous identical computers has to be global, that is, it needs $Ω(n)…

cs.DS2026

Beyond Brooks: $(Δ - 1)$ -Coloring in Semi-Streaming

Maxime Flin, Magnús M. Halldórsson

Reed [J.~Comb.~Theory B, 1999] showed that graphs of maximum degree $Δ \geq 1 0^{14}$ without $Δ$ -cliques are $(Δ - 1)$ -colorable. We design a one-pass semi-streaming algorithm for com…

cs.DS2026★ 1 cited

Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors

Maxime Flin, Magnús M. Halldórsson, Manuel Jakob +1

For any $Δ$ , let $k_{Δ}$ be the maximum integer $k$ such that $(k + 1) (k + 2) \leq Δ$ . We give a distributed \LOCAL algorithm that, given an integer $k < k_{Δ}$ , computes a valid $Δ - k$ -color…

LOCAL LLL in poly(loglogn) Rounds

Distributed Quantum Algorithms Cannot Color Cycles with Probability 1

Beyond Brooks: (Δ−1)-Coloring in Semi-Streaming

Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors

LOCAL LLL in $poly (lo g lo g n)$ Rounds

Beyond Brooks: $(Δ - 1)$ -Coloring in Semi-Streaming