Romain Cosson

Inria Paris, France

Don't hesitate to reach out!

Email: romain (dot) cosson (at) inria (dot) fr
Linkedin profile, Google scholar

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, Ali Jadbabie, Anuran Makur, and Laurent Viennot.

Publications

• 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

Recent Talks

• 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 at IHP) 2024
• PGMO Days at EDF 2024
• LABRI distributed seminar in Bordeaux 2024
• DALGO distributed seminar in Marseille 2024
• "Can we find a short path, without a map? Can we parallelize maze-solving?", Inria PhD Seminar 2024
• "Collective Tree Exploration and Layered Graph Traversal", 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
• "Competitive Analysis of Collective Tree Exploration: Can we parallelize maze-solving?", Talgo Seminar, 2023
• "Efficient Collaborative Tree Exploration with Breadth-First Depth-Next", DISC 2023
• "Additive Overhead for Online Problems", ARGO Seminar 2023
• "Reduction from Binary Classification for Universal Online Learning", COLT 2022 - video
• "Approximating the Log-Partition Function", ARGO Seminar 2022
• "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 --