Fall school of

LOGIC & COMPLEXITY

with emphasis on proof complexity

Prague 2010

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

Pictures from the school by Dai Tri Man Le.

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. Starting with the School of 2009 we interpret the "School" as "Advanced School" but the programme should be available to dedicated students, willing to learn a necessary material along the way (and perhaps study a recommended literature in advance).

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.

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

2010 Program

The 2010 school will focus on one theme only:

Extended Frege systems and beyond.

We shall concentrate on strong proof systems, a pivotal example of which is the Extended Frege system EF. While a lot of current activity in proof complexity is concentrated on very weak proof systems (e.g. variants of resolution or various algebraic proof systems), strong proof systems are neglected by many researchers. This is presumably because EF is informally linked with the class of all Boolean circuits and people may be discouraged by the apparent lack of any progress in the related field of lower bounds for general circuits, and may conclude that lower bounds for strong proof systems are impossible.

There is, however, a non-trivial body of results related to strong proof systems: links to bounded arithmetic and its model theory, relations of reflection principles and p-simulations, constructions of classes of very strong proof systems corresponding to super-exponential complexity classes, links to cryptographic primitives and to automatizability of proof search, the issue of an optimal proof system, links to the Godel's second theorem, proof complexity generators and the possibility to reduce the lengths-of-proofs lower bounds to computational hardness assumptions, combinatorial characterizations of proof size and links with quantum logic structures, non-traditional extensions of the Cook-Reckhow definition of proof systems, ... .

I think that there are further interesting facts about strong proof systems waiting to be discovered which may eventually lead to a breakthrough regarding the lower bounds. The aim of this Fall school will be to present some of this material and to discuss various possibilities for further developments.

This tutorial series will be delivered by Jan Krajicek. There will be guest speakers, including Sam Buss (U. of California, San Diego) and Phuong Nguyen (McGill U.).

A brief preliminary syllabus and background references.

A more up-to-date syllabus. Timetable, Phuong's talk.

Dates

September 20. - 24., 2010.

The program will start on Monday after lunch, at 13.oo, and will finish by Friday noon.

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, 2010.

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 (ordered alphabetically by 1st names thanks to pine, I am afraid):

Alexander V. Smal (St.Petersburg), Bruno Woltzenlogel Paleo (Nancy/Vienna), Dai Le (Toronto), Daniel Weller (Vienna), Dustin Wehr (Toronto), Emil Jerabek (Prague), Gido Scharfenberger-Fabian (Greifswald), Jakub Marecek (Nottingham), Jan Krajicek Prague), Jan Pich (Prague), Jun Tarui (Tokyo), Karel Chvalovsky (Prague), Kaveh Ghasemloo (Toronto), Klaus T. Aehlig (Munich), Konrad Zdanowski (Warsaw), Lei Huang (Toronto), Leszek Kolodziejczyk (Warsaw), Markus Latte (Muenchen), Massimo Lauria (Roma), Moritz Martin Muller (Barcelona), Neil Thapen (Prague), Nicola Galesi (Roma), Olaf Beyersdorff (Hannover), Pavel Pudlak (Prague), Phuong Nguyen (Montreal), Radek Honzik (Prague), Sam Buss (San Diego), Sebastian Muller (Prague), Stefan Hetzl (Paris), Tomas Jirotka (Prague), Yuval Filmus (Toronto), Zenon Sadowski (Bialystok), Zi Wang (Manchester/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.