Fall school of
LOGIC & COMPLEXITY
with emphasis on
Supported by the
Organization and contact:
Earlier mini-conferences: Pec'99
and Fall schools:
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
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):
Lou van den Dries,
Sam Buss, and
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).
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,
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
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
There will be guest speakers, including
(U. of California, San Diego)
and Phuong Nguyen
A brief preliminary syllabus and
A more up-to-date syllabus.
September 20. - 24., 2010.
The program will start on Monday after lunch, at 13.oo,
and will finish by Friday noon.
Faculty of Mathematics and Physics
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.
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.:
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.
information for foreign visitors of the country.