Alexandre Nolin

activity

20162026

most citedRobust Bell inequalities from communication complexity

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

collaborators

Showing 2023Show all

4 papers · 1 filter

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…

cs.DC2023

Coloring Fast with Broadcasts

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

We present an $O (lo g^{3} lo g n)$ -round distributed algorithm for the $(Δ + 1)$ -coloring problem, where each node broadcasts only one $O (lo g n)$ -bit message per round to its neighbors…

cs.CC2023

The communication complexity of functions with large outputs

Lila Fontes, Sophie Laplante, Mathieu Lauriere +1

We study the two-party communication complexity of functions with large outputs, and show that the communication complexity can greatly vary depending on what output model is consi…

cs.DC2023

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 $Δ + 1$ coloring of the graph, where $Δ$ denotes the maximum degree, it suf…