Graphs and complexity

Graphs and complexity #

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

On April 7-8, 2025, we organize two days of talks on computational complexity and graphs, in ENS Lyon.

Each talk will introduce one or several complexity classes, and present graph theory problems for which these classes play an important role, as well as proof techniques and open questions. The talks will not require any pre-requisite in complexity (beyond masters level knowledge), the goal is that each talk is accessible without specific expertise in the domain.

Location #

The talks on Monday, and on Tuesday morning will be in Amphi D2 of the Descartes campus of ENS de Lyon (15 parvis René Descartes, 69007 Lyon).

The talks on Tuesday afternoon will be in Amphi B of the Monod campus of ENS de Lyon (46 allée d’Italie, 69007 Lyon).

Both locations are easily accessible from the train stations Part-dieu and Perrache by metro or tram.

Program #

Monday, April 7, 2025 #

  • 9h30 - accueil café (next to Amphi D2)
  • 10h-11h30 - Louis Esperet : Logspace, PCP and the hardness of approximation (Amphi D2)
  • 11h45 - Repas
  • 13h30-14h20 - Alain Passelègue : Zero-knowledge proofs, interactive protocols (Amphi D2)
  • 14h30-15h20 - Frédéric Meunier : PPAD (Amphi D2)
  • 15h20 - pause (Amphi D2)
  • 16h-17h - Arnaud de Mesmay : Existential Theory of the Reals (Amphi D2)

Tuesday, April 8, 2025 #

  • 9h - accueil café (Amphi C)
  • 9h30-10h20 - Rémi Watrigant : FPT Hardness (Amphi D2)
  • 10h30-11h30 - Edouard Bonnet : Fine-grained complexity (Amphi D2)
  • 11h45 - Repas
  • 13h30-14h20 - Pascal Koiran : #P (Amphi B - Monod campus)
  • 14h30-15h30 - Eric Duchêne et Aline Parreau : PSPACE and beyond (Amphi B - Monod campus)

Hugo