Romain Cosson

Don't hesitate to reach out!

Email: romain (dot) cosson1 (at) gmail (dot) com
Linkedin profile, Google scholar

Research interests: online algorithms, inference, decision-making.

About

I am currently a Faculty Fellow in the CS department of the Courant Institute, hosted by Prof. Anupam Gupta. Before that, I defended my PhD at Inria Paris in team Argo / DI ENS, where I was advised by Prof. Laurent Massoulié. Prior to my PhD, I received a M.S. degree in computer science from MIT where I was advised by Prof. Devavrat Shah. My undergraduate was in economics and computer science as an engineer at Ecole polytechnique. I was fortunate to work with many other inspiring collaborators, among whom are Moïse Blanchard, Christian Coester, Steve Hanneke, Anuran Makur, and Laurent Viennot.

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é.
  Preprint, 2025.
• Unweighted Layered Graph Traversal
  Xingjian Bai, Christian Coester and Romain Cosson.
  35th Annual Symposium on Discrete Algorithms (SODA), 2025. [New] 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 [New] 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 Assistant

• ENS | Models and Algorithms for Networks (MAR) | Fall 2024
• ENPC | Introduction to Optimization | Fall 2023
• ENS | Randomized Algorithms (SAA) | Fall 2022, Fall 2023
• MIT | Algorithms for Inference (6.438) | Fall 2021
• Sorbonne | International Macroeconomics (L2) | Spring 2020
• Sorbonne | Intro to economics (L1) | Fall 2019
• Sorbonne | Statistics (L3) | Fall 2019
• Sorbonne | Statistics (L2) | Spring 2018

Some Talks

• 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 in the topic of collaborative exploration, above is an animated illustration. See also my interactive illustration of the tree-mining game --