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 Fall school:
by Alexander Smal and
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 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):
Lou van den Dries,
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
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
The guest speakers of this school will be:
(University of California, San Diego)
(Weizmann Institute of Science, Rehovot)
Speakers from the Prague school will include:
A syllabus is available (including
slides from some talks).
The schedule (including
Friday contributed talks).
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.
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.:
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 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),
Gido Scharfenberger-Fabian (Greifswald),
Grigory Yaroslavtsev (St.Petersbirg)
Guillaume Malod (Paris),
Hervé Fournier (Versailles),
Jakob Nordström (MIT),
Jan Hoffmann (Munich),
Kaveh Ghasemloo (Toronto),
Klaus T. Aehlig (Munchen),
Leszek Kolodziejczyk (Warsaw),
Lila Fontes (Toronto),
Lorenzo Carlucci (Roma),
Massimo Lauria (Roma),
Nicola Galesi (Roma),
Olaf Beyersdorff (Hannover),
Ran Raz (Rehovot),
Ricky Rosen (Rehovot),
R Delhi Babu (Taramani),
Sebastian Müller (Berlin),
Silvia Pragliola (Roma),
Stefan Hetzl (Paris),
Sylvain Perifel (Paris),
Yann Strozecki (Paris),
Zenon Sadowski (Bialystok),
Zofia Adamowicz (Warsaw).
information for foreign visitors of the country.