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 cs.DSShow all

7 papers · 1 filter

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…

cs.DS2025

Faster Dynamic $(Δ + 1)$ -Coloring Against Adaptive Adversaries

Maxime Flin, Magnús M. Halldórsson

We consider the problem of maintaining a proper $(Δ + 1)$ -vertex coloring in a graph on $n$ -vertices and maximum degree $Δ$ undergoing edge insertions and deletions. We give a rando…

cs.DS2024

$(Δ + 1)$ Vertex Coloring in $O (n)$ Communication

Maxime Flin, Parth Mittal

We study the communication complexity of $(Δ + 1)$ vertex coloring, where the edges of an $n$ -vertex graph of maximum degree $Δ$ are partitioned between two players. We provide a ra…

cs.DS2023

Fast Coloring Despite Congested Relays

Maxime Flin, Magnús M. Halldórsson, Alexandre Nolin

We provide a $O (lo g^{6} lo g n)$ -round randomized algorithm for distance-2 coloring in CONGEST with $Δ^{2} + 1$ colors. For $Δ ≫ poly lo g n$ , this improves exponentially…

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

Faster Dynamic (Δ+1)-Coloring Against Adaptive Adversaries

(Δ+1) Vertex Coloring in O(n) Communication

Fast Coloring Despite Congested Relays

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

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

Faster Dynamic $(Δ + 1)$ -Coloring Against Adaptive Adversaries

$(Δ + 1)$ Vertex Coloring in $O (n)$ Communication