Fall school of

LOGIC & COMPLEXITY

with emphasis on proof complexity

Prague 2009

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

Pictures from the Fall school:
by Alexander Smal and by Dai Tri Man le.

Program

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 two 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 this year 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,
and Steve Cook.

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

The special themes of this school will be

NP Search Problems

and

Algebraic computations and proofs



Search problems are fundamental computational tasks. The problem is determined by a binary relation R(x,y) with the property that for each x there is an y such that R(x,y) holds. The task is to find some solution y from an input x. The relation R is often polynomial time decidable or in the class NP. There are many natural search problems in all areas of discrete mathematics.

Search problems also naturally occur in bounded arithmetic as characterizations of classes of functions definable in various theories. The hierarchy of theories according to their strength induces a hierarchy among search problems. This is closely linked with complexity of propositional logic. Reductions between search problems are related to the existence of short proofs of one combinatorial principle from another in a specific proof system. Methods for showing non-reducibility draw directly from lower bound methods in proof complexity. Many basic questions (e.g. the existence of a complete NP search problem) are still open.

Algebraic or arithmetic circuits extend the realm of Boolean complexity to a rich context of fields and rings. There is also "algebraic" proof complexity: Algebraic proof systems (as are, for example, the Nullstellensatz proof system or Polynomial Calculus) were studied in the last ten years or so and some interesting results were obtained. In particular, these are rare proof systems for which we can describe explicitly the class of formulas with short proofs. In both areas remain fundamental open problems.

The guest speakers of this school will be:

Samuel R. Buss

(University of California, San Diego)

and

Ran Raz

(Weizmann Institute of Science, Rehovot)

Speakers from the Prague school will include:

Pavel Pudlak and Neil Thapen



A syllabus is available (including slides from some talks). The schedule (including Friday contributed talks).

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.

Dates

September 21. - 25., 2009 (arrival Sunday 20 - departure Saturday 26).

The program starts on Monday morning at 10.00.

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.

Participants:



Participants registered so far ordered alphabetically by 1st names, I am afraid (no city mentioned means a priori Prague):

Alan Johnson (San Diego), Alexander S. Kulikov (St.Petersburg), Alexander V. Smal (St.Petersburg), Andrey Breslav (St.Petersburg), Anna Yudina (St.Petersburg) Bruno Woltzenlogel Paleo (Vienna), Sam Buss (San Diego), Dai Tri Man Le (Toronto), Dasha Bogdanova (St.Petersburg), Dustin Wehr (Toronto), Ebrahim Ardeshir Larijani (Swansea), Emil Jerabek, Gido Scharfenberger-Fabian (Greifswald), Grigory Yaroslavtsev (St.Petersbirg) Guillaume Malod (Paris), Hervé Fournier (Versailles), Iddo Tzameret, Jakob Nordström (MIT), Jan Hoffmann (Munich), Jan Pich, Karel Chvalovsky, Kaveh Ghasemloo (Toronto), Klaus T. Aehlig (Munchen), Jan Krajicek, , Leszek Kolodziejczyk (Warsaw), Lila Fontes (Toronto), Lorenzo Carlucci (Roma), Massimo Lauria (Roma), Nicola Galesi (Roma), Olaf Beyersdorff (Hannover), Otto Hurtak, Pavel Patak, Pavel Pudlak, Ran Raz (Rehovot), Ricky Rosen (Rehovot), R Delhi Babu (Taramani), Samuel Carnoky, Sebastian Müller (Berlin), Silvia Pragliola (Roma), Stefan Hetzl (Paris), Sylvain Perifel (Paris), Neil Thapen, Tomas Jirotka, Veronika Stankovianska, Vitezslav Svejdar, Yann Strozecki (Paris), Zenon Sadowski (Bialystok), Zofia Adamowicz (Warsaw).

Useful information for foreign visitors of the country.