Alexandre Nolin's webpage

Research interests

My main research interests at the moment are in distributed computing and graph algorithms, especially the intersection of the two. Other topics that I find interesting and am sometimes working on include other restricted models of computation like communication complexity or streaming, the quantum versions of these models, and randomized algorithms in general.

Publications

• Optimal Deterministic Rendezvous in Labeled Lines

  with Y. Bourreau and A. Narayanan
  STACS (2026) version (soon) PODC (2025) BA version arXiv full version

• Faster Distributed Δ-Coloring via a Reduction to MIS

  with Y. Bourreau and S. Brandt
  SODA (2026) arXiv version

• Decentralized distributed graph coloring: Cluster graphs

  with M. Flin and M. M. Halldórsson
  PODC (2025) version arXiv full version

• Faster Distributed Δ-Coloring via Ruling Subgraphs

  with Y. Bourreau and S. Brandt
  STOC (2025) version arXiv full version

• Decentralized distributed graph coloring II: degree+1-coloring virtual graphs

  with M. Flin and M. M. Halldórsson
  DISC (2024) version arXiv full version

• Content-oblivious leader election on rings

  with F. Frei, R. Gelles, and A. Ghazy
  DISC (2024) version PODC (2024) BA version arXiv full version

• A distributed palette sparsification theorem

  with M. Flin, M. Ghaffari, M. M. Halldórsson, and F. Kuhn
  SODA (2024) arXiv version

• Fast coloring despite congested relays

  with M. Flin and M. M. Halldórsson
  DISC (2023) version arXiv full version

• Distributed coloring of hypergraphs

  with D. Adamson and M. M. Halldórsson
  SIROCCO (2023) version author proof

• The communication complexity of functions with large outputs

  with L. Fontes, S. Laplante, and M. Laurière
  SIROCCO (2023) version arXiv full version
  Best paper award at SIROCCO 2023

• Coloring fast with broadcasts

  with M. Flin, M. Ghaffari, M. M. Halldórsson, and F. Kuhn
  SPAA (2023) version arXiv full version

• Fast distributed vertex splitting with applications

  with M. M. Halldórsson and Y. Maus
  DISC (2022) version arXiv full version

• Overcoming congestion in distributed coloring

  with M. M. Halldórsson and T. Tonoyan
  PODC (2022) version arXiv full version

• Near-optimal distributed degree+1 coloring

  with M. M. Halldórsson, F. Kuhn, and T. Tonoyan
  STOC (2022) version arXiv full version
  pdf of poster

• Superfast coloring in CONGEST via efficient color sampling

  with M. M. Halldórsson
  Theoretical Computer Science (2023) version SIROCCO (2021) version arXiv full version
  Best paper award at SIROCCO 2021

• Communication complexity: large output functions, partition bounds, and quantum nonlocality

  (PhD thesis) advised by S. Laplante
  Eprint (HAL) version

• Coloring fast without learning your neighbors' colors

  with M. M. Halldórsson, F. Kuhn, and Y. Maus
  DISC (2020) version arXiv full version

• Distributed testing of distance-k colorings

  with P. Fraigniaud and M. M. Halldórsson
  SIROCCO (2020) version early draft

• Robust Bell inequalities from communication complexity

  with S. Laplante, M. Laurière, J. Roland, and G. Senno
  Quantum (2018) version TQC (2016) version
  Best poster award at QIP 2017(partial) pdf of poster

• Efficient and practical tree preconditioning for solving Laplacian systems

  with L. Castelli Aleardi and M. Ovsjanikov
  SEA (2015) version Eprint (HAL) version

Public preprints

• Ultrafast Distributed Coloring of High Degree Graphs

  with M. M. Halldórsson and T. Tonoyan
  arXiv version

See also my dblp record, my orcid, my HAL cv, and my arXiv page.

Teaching

I was involved in the teaching of the following classes in previous years:

At Saarland University

• Impossibility Results of Local Algorithms (2024-2025), as seminar co-organizer
• An Extravaganza of Algorithmic models (2023-2024), as seminar co-organizer
• Distributed graphs algorithms (2022-2025), various tasks (TA, exam design, grading, replacement lecturer)

At Reykjavik University

• Algorithms (2021-2022), as lecturer

At Paris Diderot University (now part of Paris Cité University)

• Programming in C (2018-2019), as TA
• Internet and tools (2018-2019), as TA
• Tools for the analysis of algorithms (2017-2018 and 2018-2019), as TA
• Object-oriented programming and graphical user interfaces (2016-2017 and 2017-2018), as TA
• Computer science project (2015-2016), as TA
• Principles of operation of binary machines (2015-2016), as TA

At Ecole polytechnique

• Algorithmic riddles (2014-2015), as TA

Community service

• PC member for ICDCN 2026
• PC member for PODC 2025
• PC member for ICDCN 2025
• PC member for SIROCCO 2024
• Proceedings chair for PODC 2023

Some talks

You may have seen me as an invited speaker at one of the following events.

• At AMG 2025, giving a talk titled "On Coloring Embedded Graphs" (slides)
• At WAND 2024, giving a talk titled "Coloring a Mostly Forgotten Graph" (slides)
• At ADGA 2023, giving a talk titled "Pseudorandomness: some distributed applications" (slides)

Employment

I have been at the following institutes:

• At Télécom SudParis (Evry, France) as an associate professor (maître de conférence), since November 2025.
• At the CISPA Helmholtz Center for Information Security (Saarbrücken, Germany) as a postdoc in the group of Sebastian Brandt, from 2022 to 2025.
• At Reykjavik University (Reykjavik, Iceland) as a postdoc in the group of Magnús M. Halldórsson, from 2020 to 2022.
• At Paris Cité University (Paris, France) as a Ph.D. student, advised by Sophie Laplante, from 2015 to 2020 (formerly known as Paris Diderot University until 2019, and as the University of Paris from 2019 to 2022)

Languages

Computer ones

• Python3
• Java
• C, C++
• HTML, CSS
• PHP
• SQL

Human ones

• French (native)
• English (fluent)
• German (enough to get by)