Fall school of

LOGIC & COMPLEXITY

Prague 2011

The 2011 Fall school is a part of activities of MALOA (Mathematical Logic and Applications), a Marie Curie Initial Training Network, and partially supported by it.
It will be the first event of a special semester in Logic and Complexity held at the Charles University in Prague.

Organization and contact: Jan Krajicek.

Earlier mini-conferences: Pec'99 and Pec'00 ,
and Fall schools: Pec'01, Pec'02, Pec'03, Pec'04, Pec'05, Trest'07, Prague'08, Prague'09, and Prague'10.

Pictures from the 2011 school by Sasha Smal.

The broad theme of the Fall schools is the interaction of Mathematical Logic and Complexity Theory, with a special emphasis on Proof Complexity. A typical format of the school is this: We have one or more series of lectures during Monday to Thursday, each usually two hours per day. Some lectures (sometimes most of them) in the series are delivered by guest speakers on a topic in logic or complexity theory broadly relevant to the main theme of the schools.

Past guest speakers were (in the order of appearance):

Tomas Jech,
Lou van den Dries,
Johan Hastad,
Ulrich Kohlenbach,
Russell Impagliazzo,
Jeff Paris,
Stevo Todorcevic,
Albert Atserias,
Steve Cook,
Sam Buss, and
Ran Raz.

In addition, Prague logicians, including Emil Jerabek, Jan Krajicek, Pavel Pudlak and Neil Thapen, have repeatedly contributed lectures.

This programme is traditionally complemented by lectures of the participants on their own work (relevant to the topics of the year) during a part of Friday (there is no obligation to deliver such a talk, though).

2011 Program

The 2011 school aims at presenting several active topics in the general area of

Interaction between logic and complexity

There will be

two tutorial series:

  • Anuj Dawar (Cambridge): Descriptive polynomial time complexity

  • Emil Jerabek (Prague): Bounded arithmetic

    presented in a manner accessible to students with a general background in logic and computational complexity but with no special training in the area, and several more advanced

    individual 1-2 hours talks:

  • 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

    Schedule



    Dates

    September 19. - 23., 2011.

    The program will start on Monday morning and will finish Friday afternoon.

    Place

    Faculty of Mathematics and Physics
    Charles University
    Prague

    The venue's address is: Sokolovska 83, Praha 8.
    This is just behind the corner from Metro line B stop "Krizikova". Also trams nb.8 and 24 stop in front of the building.
    Lecture hall: K1 on the second floor.

    Participants:

    If you are interested to participate, please register with me, and preferably before the

    deadline May 15, 2011.

    If you have not participated in an earlier Fall school, please outline briefly your academic background.
    Everybody is, in principle, welcome to participate.

    Participants registered so far:

    Klaus Aehlig (Munich), Christoph Berkholz (Berlin), Lyosha Beshenov (St.Petersburg), Ivan Bliznets (St.Petersburg), Elena Botoeva (Bolzano), Karel Chvalovsky (Prague), Anupam Das (Bath), Aleksey Davydow (St.Petersburg), Anuj Dawar (Cambridge), Yuval Filmus (Toronto), Luke Friedman (Rutgers), Michal Garlik (Prague), Kaveh Ghasemloo (Toronto), Jana Glivicka (Prague), Alex Golovnev (St.Petersburg), Bruce Kapron (Victoria), Volha Kerhet (Bolzano), Pascal Koiran (Lyon), Jan Krajicek (Prague), Stephan Kreutzer (Berlin), Lukas Mach (Prague), Dai Tri Man Le (Toronto), Sebastian Muller (Prague), Sergi Oliva (Barcelona), Vsevolod Oparin (St.Petersburg), Marco Pazzaglia (Udine), Jan Pich (Prague), Pavel Pudlak (Prague), Zenon Sadowksi (Bialystok), Alexander Smal (St.Petersburgh), Neil Thapen (Prague), Anton Timofeev (St.Petersburg), Tomas Toufar (Prague), Angelos Tsolakis (Cambridge), Jonathan Verner (Prague), Zi Wang (Prague).

    Accommodation and board

    Prague has a wide spectrum of accommodation, ranging from cheap hostels to pensions and hotels.
    For example, a web page maintained by the city hall has several links. Other sites with accommodation information are e.g.: expats.cz and Prague.tv

    Everybody is expected to take care of his or her accommodation. You may use a list of nearby hotels.

    There is no conference fee. Everybody pays only his or her expenses. I may collect at the start of the school some small amount to cover for coffee and tea available during breaks.

    Useful information for foreign visitors of the country.