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.

Program #

Monday, April 7, 2025 #

9h30 - accueil café (next to Amphi D2)
10h-11h30 - Louis Esperet : Logspace, PCP and the hardness of approximation (slides) You can also look at lectures 3 and 4 on this webpage for more detailed explanations.
11h45 - Repas
13h30-14h20 - Alain Passelègue : Zero-knowledge proofs, interactive protocols (slides)
14h30-15h20 - Frédéric Meunier : PPAD (slides)
15h20 - pause
16h-17h - Arnaud de Mesmay : Existential Theory of the Reals (slides)

Tuesday, April 8, 2025 #

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

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.

Acknowledgement #

Many thanks to LIP, G-SCOP, and the ANR for the financial and administrative support.