Complexity (30 January – 3 February)

Schedule

Monday 30

11:00 - 12:30
Lecture Yiannis N. Moschovakis (UCLA, USA) Relative complexity in arithmetic and algebra — part 1
14:30 - 15:00
Contributed talk Pierre Valarcher (Université Paris Est Créteil) From intentional behavior to algorithmic completeness.
15:00 - 15:30
Contributed talk Ugo Dal Lago (University of Bologna) Higher-order Interpretations and Program Complexity (joint work with Patrick Baillot).
16:00 - 16:30
Contributed talk Isabel Oitavem (FCT-UNL and CMAF-UL) NP with tier 0 pointers.
16:30 - 17:00
Contributed talk Reinhard Kahle (Universidade Nova de Lisboa) Computational Complexity and Applicative Theories (joint work with Isabel Oitavem).

Tuesday 31

9:00 - 10:30
Lecture Martin Hofmann (LMU, Munich, Germany) Pure pointer programs (implicit computational complexity) with an abstract datatype of pointers — part 1
11:00 - 12:30
Lecture Yiannis N. Moschovakis (UCLA, USA) Relative complexity in arithmetic and algebra — part 2
14:30 - 16:00
Invited talk Emmanuel Hainry (Nancy) Computable Analysis: Computability and complexity over the reals
16:30 - 17:00
Contributed talk Marco Solieri (Université Paris 13) Deep into optimality Complexity and correctness of shared implementation of bounded logics.
17:00 - 17:30
Contributed talk Matthieu Perrinel (ENS Lyon) Strong bound for light linear logic by levels

Wednesday 1

9:00 - 10:30
Lecture Martin Hofmann (LMU, Munich, Germany) Pure pointer programs (implicit computational complexity) with an abstract datatype of pointers — part 2
11:00 - 12:30
Invited talk Neil Jones (Copenhagen) Alan Turing and 75 years of research in models of computation
13:45 - 15:00
Hippocampe: poster session by young (high school) mathematicians

Thursday 2

9:00 - 10:30
Lecture Heribert Vollmer (Leibniz Universität, Hannover, Germany) Circuit complexity — Arithmetic circuits of small depth
11:00 - 12:30
Lecture Stefan Szeider (TU Wien, Austria) Parametrized complexity — part 1
14:30 - 16:00
Invited talk Virgile Mogbil (LIPN, Paris Nord) Parallel computation with boolean proof nets
16:00 - 16:30
Contributed talk Clément Aubert (LIPN - Univ. Paris 13) Proof circuits and others parallel models of computation.

Friday 3

9:00 - 10:30
Lecture Stefan Szeider (TU Wien, Austria) Parametrized complexity — part 2
11:00 - 12:30
Lecture Heribert Vollmer (Leibniz Universität, Hannover, Germany) Circuit complexity — Proof complexity
14:00 - 14:30
Contributed talk Martin Lackner (Vienna University of Technology) Fixed-Parameter Algorithms for Finding Minimal Models (joint work with Andreas Pfandler).
14:00 - 16:00
Contributed talks
14:30 - 15:00
Contributed talk Johannes Schmidt (Université de Marseille) On the Parameterized Complexity of Default Logic and Autoepistemic Logic.