Complexity (30 January – 3 February)
The theme of this week is the logical approach to logical complexity. The last decade has seen the development of logical formalisms derived from linear logic that characterize functions computable in various complexity classes (polynomial or elementary in time, logarithmic in space) in an implicit way, that is to say by contruction of the languages instead of using explicit measures. The theory that underlies these formalisms naturally meets the more established tradition of studying the complexity of algorithmic problems from logic (satisfiability, constraints solving, etc). The goal of this week is to survey the various aspects of the theory of algorithmic complexity where these communities meet, so as to trigger new interactions and enrich the various approaches.
Lecturers
- Martin Hofmann (LMU, Munich, Germany)
- Yiannis N. Moschovakis (UCLA, USA)
- Stefan Szeider (TU Wien, Austria)
- Heribert Vollmer (Leibniz Universität, Hannover, Germany)
Invited speakers
- Emmanuel Hainry (Nancy)
- Neil Jones (Copenhagen)
- Virgile Mogbil (LIPN, Paris Nord)
Programme
The programme is available here. A printable version with abstracts is also available as pdf.
The morning sessions will consist in tutorials given by invited speakers while the afternoons will be devoted to shorter presentations and contributed talks.
Call for contributions
Abstract and title must be submitted electronically to the three organizers:
- patrick.baillot@ens-lyon.fr
- nadia.creignou@lif.univ-mrs.fr
- jean-yves.marion@loria.fr
Submissions of abstracts on published work is allowed.
Important dates:
- Abstract submission: December, 15th, 2011
- Notification: January, 3rd, 2012