Complexity Days - Sciencesconf.org

9:00 - 10:00 (1h)

Complexity Theory for Real-World Computation

Amphi Pierre-Gilles de Gennes

Jakob Nordström

10:00 - 10:30 (30min)

Coffee break

10:30 - 11:00 (30min)

Enumeration complexity and regularization

Amphi Pierre-Gilles de Gennes

Yann Strozecki

11:00 - 11:30 (30min)

Triple mutual information: combinatorial and communication perspectives

Amphi Pierre-Gilles de Gennes

Andrei Romaschenko

11:30 - 12:00 (30min)

Scheduling meets parameterized complexity

Amphi Pierre-Gilles de Gennes

Maher Mallem

12:00 - 14:00 (2h)

Lunch (Restaurant Buffon)

14:00 - 15:00 (1h)

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits : An overview

Amphi Pierre-Gilles de Gennes

Sébastien Tavenas

15:00 - 15:30 (30min)

Coffee break

15:30 - 16:00 (30min)

Specification and Automatic Verification of Computational Reductions

Amphi Pierre-Gilles de Gennes

Julien Grange

16:00 - 16:20 (20min)

Characterisations of polynomial-time and -space complexity classes over the reals

Amphi Pierre-Gilles de Gennes

Manon Blanc

16:20 - 16:40 (20min)

Coming up with new solutions independently : A simple to state but hard to solve combinatorial problem with links to time bounded Kolmogorov complexity

Amphi Pierre-Gilles de Gennes

Ulysse Léchine

16:40 - 17:00 (20min)

Closing discussion

Amphi Pierre-Gilles de Gennes

	Wed. 13	Thu. 14
09:00 10:00 11:00 12:00 13:00 14:00 15:00 16:00 17:00 18:00 19:00 20:00 21:00 22:00	Arrival and coffee 13:30 - 13:50 (20min) Arrival and coffee Opening remarks 13:50 - 14:00 (10min) Opening remarks Amphi Turing Certificate games 14:00 - 15:00 (1h) Certificate games Amphi Turing Sophie Laplante Coffee break 15:00 - 15:30 (30min) Coffee break The Descriptive Complexity of Graph Neural Networks 15:30 - 16:30 (1h) The Descriptive Complexity of Graph Neural Networks Amphi Turing Martin Grohe Break 16:30 - 16:45 (15min) Break Implicit characterization of the class of Basic Feasible Functionals 16:45 - 17:15 (30min) Implicit characterization of the class of Basic Feasible Functionals Amphi Turing Romain Péchoux Characterization of complexity classes using categorical logic 17:15 - 17:40 (25min) Characterization of complexity classes using categorical logic Amphi Turing Baptiste Chanus The expressive power of low descriptive complexity invariants 17:40 - 18:00 (20min) The expressive power of low descriptive complexity invariants Amphi Turing Djamel Amir Dinner (Restaurant Bouillon Racine) 19:45 - 22:00 (2h15) Dinner (Restaurant Bouillon Racine)	Complexity Theory for Real-World Computation 9:00 - 10:00 (1h) Complexity Theory for Real-World Computation Amphi Pierre-Gilles de Gennes Jakob Nordström Coffee break 10:00 - 10:30 (30min) Coffee break Enumeration complexity and regularization 10:30 - 11:00 (30min) Enumeration complexity and regularization Amphi Pierre-Gilles de Gennes Yann Strozecki Triple mutual information: combinatorial and communication perspectives 11:00 - 11:30 (30min) Triple mutual information: combinatorial and communication perspectives Amphi Pierre-Gilles de Gennes Andrei Romaschenko Scheduling meets parameterized complexity 11:30 - 12:00 (30min) Scheduling meets parameterized complexity Amphi Pierre-Gilles de Gennes Maher Mallem Lunch (Restaurant Buffon) 12:00 - 14:00 (2h) Lunch (Restaurant Buffon) Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits : An overview 14:00 - 15:00 (1h) Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits : An overview Amphi Pierre-Gilles de Gennes Sébastien Tavenas Coffee break 15:00 - 15:30 (30min) Coffee break Specification and Automatic Verification of Computational Reductions 15:30 - 16:00 (30min) Specification and Automatic Verification of Computational Reductions Amphi Pierre-Gilles de Gennes Julien Grange Characterisations of polynomial-time and -space complexity classes over the reals 16:00 - 16:20 (20min) Characterisations of polynomial-time and -space complexity classes over the reals Amphi Pierre-Gilles de Gennes Manon Blanc Coming up with new solutions independently : A simple to state but hard to solve combinatorial problem with links to time bounded Kolmogorov complexity 16:20 - 16:40 (20min) Coming up with new solutions independently : A simple to state but hard to solve combinatorial problem with links to time bounded Kolmogorov complexity Amphi Pierre-Gilles de Gennes Ulysse Léchine Closing discussion 16:40 - 17:00 (20min) Closing discussion Amphi Pierre-Gilles de Gennes