Alexandre Nolin's webpage

Research interests

My main interests are communication complexity, distributed computing, and quantum computing. More broadly, I am interested in restricted models of computation and algorithms in general.

Publications

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

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

• Content-oblivious leader election on rings

  with F. Frei, R. Gelles, and A. Ghazy
  DISC (2024) version (soon) 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

• Decentralized distributed graph coloring: Cluster graphs

  with M. Flin, and M. M. Halldórsson
  arXiv version

• Ultrafast Distributed Coloring of High Degree Graphs

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

See also my dblp record and my orcid.

Teaching

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

At Saarland University

• An Extravaganza of Algorithmic models (2023-2024), as seminar organizer
• Distributed graphs algorithms (2022-2023 and 2023-2024), as TA and other tasks (exam design, grading)

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 2025
• PC member for SIROCCO 2024
• Proceedings chair for PODC 2023