Romain Cosson

Email: romain (dot) cosson (at) nyu (dot) edu
Linkedin, Scholar
Don't hesitate to reach out!

Interests: algorithms, learning, decision-making.

About

I am an Assistant Professor / Faculty Fellow in the CS department at the Courant Institute at NYU, hosted by Prof. Anupam Gupta. My research lies at the intersection of algorithms, optimization, and decision-making. I am particularly interested in online algorithms, which are algorithms that must make decisions sequentially without knowing the future. I defended my PhD at Inria Paris in the team Argo joint with DI ENS, where I was advised by Prof. Laurent Massoulié. Before that, I received a M.S. degree in computer science from MIT where I was advised by Prof. Devavrat Shah in LIDS. My undergraduate was in applied mathematics as an engineer at Ecole polytechnique.

Illustrations

(a) Collective Exploration

(b) Ultrametric Traversal

(c) Random Cones

Publications

• Non-clairvoyant scheduling with progress bars
  Ziyad Benomar, Romain Cosson, Alexander Lindermayr, Jens Shlöter.
  39th Conference on Neural Information Processing Systems (NeurIPS), 2025 (Spotlight).
• Asynchronous Collective Tree Exploration: a Distributed Algorithm and a new Lower Bound
  Romain Cosson and Laurent Massoulié. illustration
  Preprint, 2025.
• Unweighted Layered Graph Traversal
  Xingjian Bai, Christian Coester and Romain Cosson.
  35th Annual Symposium on Discrete Algorithms (SODA), 2025. illustration and short video
• Barely Random Algorithms for Metrical Task Systems
  Romain Cosson and Laurent Massoulié.
  38th Conference on Neural Information Processing Systems (NeurIPS), 2024 (Spotlight). short video
• Collective Tree Exploration via Potential Function Method
  Romain Cosson and Laurent Massoulié.
  15th Innovations in Theoretical Computer Science (ITCS), 2024.
• Breaking the k/log k Barrier in Collective Tree Exploration via Tree-Mining
  Romain Cosson.
  35th Annual Symposium on Discrete Algorithms (SODA), 2024.
• Efficient Collaborative Tree Exploration with Breadth-First Depth-Next
  Romain Cosson, Laurent Massoulié and Laurent Viennot.
  37th International Symposium on Distributed Computing (DISC), 2023. download version and exercise
  Announced at 42nd Symposium on Principles of Distributed Computing (PODC), 2023. download version
• Approximating the Log-Partition Function
  Romain Cosson.
  Master Thesis. Massachusetts Institute of Technology, 2021. download paper
• Universal Online Learning with Bounded Loss: Reduction to Binary Classification
  Moïse Blanchard and Romain Cosson.
  35th Annual Conference on Learning Theory (COLT), 2022.
• Universal Online Learning with Unbounded Losses: Memory Is All You Need
  Moïse Blanchard, Romain Cosson and Steve Hanneke.
  33rd International Conference on Algorithmic Learning Theory (ALT), 2022.
• Quantifying Variational Approximation for the Log-Partition Function
  Romain Cosson and Devavrat Shah.
  34th Annual Conference on Learning Theory (COLT), 2021.

Teaching

• NYU | Data Structures (CS 102) | Fall 2025, Spring 2026 | Lecture [Syllabus]
• ENS | Models and Algorithms for Networks (MAR) | Fall 2024 | TD
• ENPC | Introduction to Optimization | Fall 2023 | TD
• ENS | Randomized Algorithms (SAA) | Fall 2022, Fall 2023 | TD
• MIT | Algorithms for Inference (6.438) | Fall 2021 | TD
• Sorbonne | International Macroeconomics (L2) | Spring 2020 | TD
• Sorbonne | Intro to economics (L1) | Fall 2019 | TD
• Sorbonne | Statistics (L3) | Fall 2019 | TD
• Sorbonne | Statistics (L2) | Spring 2018 | TD

Some Talks

• NYU convexity seminar, Courant Institute, 2026
• DIMACS seminar, Rutgers University, 2026
• NYU theory seminar, Courant Institute, 2025
• Cermics Seminar, Ecole des Ponts, 2025
• FairPlay Seminar, Criteo & Ensae, 2025
• Les Houches winter school of Physics - video
• "Unweighted layered graph traversal", SODA 2025
• Darmstadt TU optimization seminar 2024
• Complexity and Algorithms Workshop (CoA @ IHP) 2024
• PGMO Days at EDF 2024
• LABRI distributed seminar in Bordeaux 2024
• DALGO distributed seminar in Marseille 2024
• Inria PhD Seminar 2024
• ALGORIDAM Seminar 2024
• "Collective Tree Exploration via Potential Function Method", ITCS 2024 - video
• "Breaking the k/log k Barrier in Collective Tree Exploration via Tree-Mining", SODA 2024 - video
• Talgo Seminar, ENS, 2023
• "Efficient Collaborative Tree Exploration with Breadth-First Depth-Next", DISC 2023
• "Reduction from Binary Classification for Universal Online Learning", COLT 2022 - video
• "Approximating the Log-Partition Function", COLT 2021 - video

I am interested by exploration problems. In the video above, a team of 30 robots is exploring a tree-maze embedded in a 300x300 square. Unexplored nodes are shaded.