Seminar Details
Online Algorithms for Multi-agent Exploration
- Start Date: March 4, 2026
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Romain Cosson - New York University (NYU)
- Event Location: CoRE Building Room 431
- Presentation Type: Stand Alone Presentation
- Abstract:
Abstract: Is maze-solving parallelizable? Can you find a short path, without a map? These two algorithmic questions can be rigorously formalized (via competitive analysis) and analyzed (using convex regularization). In this presentation, I will explain how they are connected and use them as a lens on broader themes in online decision-making, such as collective intelligence, advice complexity, randomized complexity, and average-case analysis. A (2D) illustration of collective exploration is available here: https://romcos.github.io/html/cte/index.html.