Title: Collective algorithms for exploration and decision-making
Date: Friday July 11th, 2pm (Paris)
Abstract:
Can you find a short path, without a map? Is maze-solving parallelizable? These seemingly simple questions
reveal deep algorithmic challenges that can be rigorously explored using the toolbox of competitive analysis and
other techniques that have been developed over the years since the 1990s. In this presentation, I will describe
the connexions between these problems and use them as a case study of general challenges arising in online
decision-making such as: collective intelligence, advice complexity, randomized complexity and average-case
analysis.
The jury will be composed of — joining in person — Anupam Gupta (rapporteur), Laurent Massoulié (thesis supervisor), Claire Mathieu, Vianney Perchet and — joining online — Christian Coester, Yuval Rabani (rapporteur), Devavrat Shah.
The manuscript is based on joint works with Xingjian Bai, Christian Coester, Laurent Massoulié and Laurent Viennot.
Location (in person): Inria, Paris, 48 rue Barrault, 75013, salle Jacques Louis Lions.
If you plan to attend, register here: https://forms.gle/qrTZgMuh22NZSJLe9
Webex link (online): register at https://forms.gle/qrTZgMuh22NZSJLe9 to receive the Webex link!
Looking forward to seeing you!
Titre : Algorithmes collectifs pour l’exploration et la prise de décision
Date : Vendredi 11 juillet à 14h
Résumé :
Peut-on trouver un chemin court sans carte ? Peut-on paralléliser la résolution d’un labyrinthe ? Ces questions,
en apparence simples, révèlent des défis algorithmiques qui peuvent être explorés rigoureusement à l’aide
d’outils comme l’analyse compétitive et d’autres techniques développées depuis les années 1990. Dans cette
présentation, je décrirai les liens entre ces problèmes et les utiliserai comme étude de cas pour illustrer des
enjeux plus généraux de la prise de décision en ligne, tels que l’intelligence collective, la complexité en
conseils, la complexité randomisée et l’analyse en moyenne.
Le jury sera composé de — en présentiel — Anupam Gupta (rapporteur), Laurent Massoulié (directeur de thèse), Claire Mathieu, Vianney Perchet et — en ligne — Christian Coester, Yuval Rabani (rapporteur), Devavrat Shah.
Le manuscrit est basé sur des travaux en collaboration avec Xingjian Bai, Christian Coester, Laurent Massoulié et Laurent Viennot.
Lieu (présentiel) : Inria, Paris, 48 rue Barrault, 75013, salle Jacques-Louis Lions.
Pour confirmer votre participation : https://forms.gle/qrTZgMuh22NZSJLe9
Lien Webex (en ligne) : inscrivez-vous à https://forms.gle/qrTZgMuh22NZSJLe9 pour recevoir le lien de connexion.
Hâte de vous voir !