Fall School 2011 of Logic & Complexity (Prague)
by Massimo Lauria
Today is the first day of the Fall School of Logic & Complexity 2011 which runs from September 19th to September 23th. The school is also the opening act of the special semester in logic and complexity that has been organized here in Prague. Prague.
The school has been running in various incarnations since 1999, and as far as I know it has always been organized by Jan Kraíček. The school focuses on topics of logic applied in the context of computational complexity.
The speakers of this year are
- Anuj Dawar (Cambridge): Descriptive polynomial time complexity.
Descriptive complexity studies the possibility to characterize various complexity classes in some logic. The ideal outcome would be to have a language such that a predicate can be expressed in it if and only if it is polynomially decidable.
- Emil Jeřábek (Prague): Bounded arithmetic.
Bounded arithmetics are weak sub-theories of Peano Arithmetic. They are defined in such a way to limit the set of functions on which they can prove things. In particular such theories have been developed to capture functions of limited computational complexity. The typical theorem in Bounded Arithmetic looks like “a theory proves that a function is total if and only if the function belongs to a complexity class ”.
Other that the two main lecture series, there are shorter tutorials (one or two talks each) on topics related to the school.
- Pascal Koiran (Lyon): Shallow circuits with high-powered inputs;
- Stephan Kreutzer (Berlin): The Complexity of Evaluating Formulas in Relational Structures;
- Pavel Pudlak (Prague): Randomness, pseudorandomnesss and models of arithmetic;
- Neil Thapen (Prague): The provably total NP search problems of weak second order bounded arithmetic.
On the webpage of the school there are detailed description of every lecture series. Also references and reading material are given in some cases.