Journées CALAMAR 2025 - Graphes et complexité #

Organisation: Edouard Bonnet, Louis Esperet, Rémi Watrigant

Les 7 et 8 avril 2025 nous organisons à l’ENS de Lyon (en présentiel) deux journées d’exposés sur le thème de la complexité, à destination des membres de toute la communauté graphes et algorithmes. Merci de nous prévenir par mail si vous comptez venir, pour que nous puissions calibrer les salles).

Chaque exposé abordera une ou plusieurs classes de complexité, et présentera des problèmes de graphes pour lesquels ces classes jouent un rôle important, ainsi que des techniques de preuves et des questions ouvertes. Les exposés ne demanderont pas de pré-requis en complexité, le but est que chaque exposé soit abordable sans aucune expertise dans ce domaine.

Programme prévisionnel #

Les exposés devraient commencer autour de 9h30-10h le lundi matin, et finir vers 16h mardi.

• Logspace - Louis Esperet
• Zero-knowledge proofs, interactive protocols - Alain Passelègue
• Classes de difficulté FPT - Rémi Watrigant
• Théorie existentielle des réels - Arnaud de Mesmay
• PSPACE et au-delà - Éric Duchêne ou Aline Parreau
• #P - Pascal Koiran
• PPAD - Frédéric Meunier
• Fine-grained complexity - Édouard Bonnet