Fall school of

LOGIC & COMPLEXITY

with emphasis on proof complexity

Prague 2008

Supported by the Charles University.

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, and Trest'07.

Program

The broad theme of the Fall schools is the interaction of Mathematical Logic and Complexity Theory, with special emphasis on Proof Complexity.

The format of the school is this: We have two tutorials during Monday to Thursday, each usually two hours per day. One tutorial is delivered by the main guest speaker 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,
and Albert Atserias.

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

The main guest speaker of this school will be:

Stephen A. Cook

(University of Toronto)

who will deliver a series of lectures on:

Formal reasoning using low-complexity concepts

Content:
I will talk about the idea of limiting the concepts of a proof to a particular complexity class, giving examples of what can and (apparently) cannot be proved in various complexity classes. I will explain how to formalize these theories as two-sorted systems, giving examples, and talk about associating quantified propositional proof systems with the theories, including propositional translations and reflection principles. (4 lectures)

The second tutorial series will concentrate on recent advances in

Proof Complexity

and will be given by members of the Prague school and their guests:

  • K.Aehlig: Notations for proofs, (joint work with A.Beckmann, 2 lectures)

  • J.Krajicek: Problems and perspectives in proof complexity (3 lectures)

  • P.Pudlak: Feasible Incompleteness Thesis (1 lecture)

  • I.Tzameret: Bounds on equational proofs of polynomial identities (joint work with P.Hrubes, 2 lectures)

    Friday will be devoted to lectures of participants on their own work and possibly to a problem session - this will be organized during the School.

    Schedule is provisional at this point - check closer to the event.

    Place

    Faculty of Mathematics and Physics
    Charles University
    Prague

    The venue's address is: Sokolovska 83, Praha8.
    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: K4 on the ground floor.

    Dates

    September 22. - 26., 2008 (arrival Sunday 21 - departure Saturday 27).

    The program starts on Monday at 9.45.

    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. I shall help with the accommodation arrangments to people who will ask before the deadline below.

    There is no conference fee. Everybody pays only his or her expenses.

    Participants:

    Participants registered so far:

    Zofia Adamowicz (Warsaw), Klaus Aehlig (Swansea), Olaf Beyersdorff (Hannover), Stefano Cavagnetto (Prague), Steve Cook (Toronto), Dmitry Gavinsky (Princeton), Zuzana Hanikova (Prague), Jan Hoffmann (Muenchen), Otto Hurtak (Prague), Karel Chvalovsky (Prague), Emil Jerabek (Prague), Alan Johnson (San Diego), Tomas Kadlcek (Prague), Peter Kalnai (Prague), Leszek Kolodziejczyk (Warsaw), Michal Koucky (Prague), Jan Krajicek (Prague), Ema Krejcova (Prague), Antonin Kucera (Prague), Ondrej Kuncar (Prague), Andy Lamperski (Caltech), Ebrahim Ardeshir Larijani (Swansea), Markus Latte (Muenchen), Jakub Marecek (Nottingham), Sebastian Muller (Berlin), Pavel Patak (Prague), Michal Pelis (Prague), Jan Pich (Prague), Frantisek Polach (Prague), Pavel Pudlak (Prague), Zenon Sadowski (Bialystok), Gido Scharfenberger-Fabian (Berlin), Alexander Smal (St.Petersburgh), Martin Suda (Prague), Vitezslav Svejdar (Prague), Jun Tarui (Tokyo), Neil Thapen (Prague), Phuong The Nguyen (Toronto/Prague), Kostas Tsaprounis (Illinois), Iddo Tzameret (Tel Aviv/Prague), Alena Vencovska (Manchester).

    Useful information for foreign visitors of the country.