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 litarature 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 explicitely the class of formulas with short proofs.
In both areas remain fundamental open
problems.
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.
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
I will also provide later a list of a few
nearby hotels and pensions.
Everybody is expected to take care of his or her accommodation.
I shall help with the
accommodation arrangements to people who will ask before the deadline below.
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:
If you are interested to participate, please register
with me, and
preferably before the
deadline April 15, 2009.
If you have not participated in an earlier Fall school,
please outline briefly your academic background.
Everybody is, in principle, welcome to participate.
We are somewhat limited by available space (maximum of 50
participants) so priority
will be given to people active in logic and/or complexity
theory, and among those to doctoral
students and postdocs. I will try to accommodate also
late applicants
but I cannot guarantee that there will be enough space.
Important request:
I request that when you register you are reasonably sure of
your intentions to really come: People
canceling just before the meeting
are hard to replace by other participants and
the cancellation simply results in a loss of a slot.
Useful
information for foreign visitors of the country.
