21-25 Sep 2009
Prague, Czech Republic
========================================================
Call for Participation
Fall School of LOGIC & COMPLEXITY:
NP Search Problems and Algebraic Computation
Prague, 21-25 September 2009
http://www.math.cas.cz/~krajicek/fall09.html
==========================================================
Guest Speakers:
* Samuel R. Buss (University of California, San Diego)
* Ran Raz (Weizmann Institute of Science, Rehovot)
Speakers from the Prague School will include:
* Pavel Pudlak
* Neil Thapen
Organization and contact: Jan Krajicek (krajicek@math.cas.cz)
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 school.
Starting this year we interpret the "School" as "Advanced School" but
the program should be available to dedicated students, willing to
learn a necessary material along the way (and perhaps study a
recommended literature in advance).
The special themes of this fall school will be:
1) NP Search Problems
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 a y such that R(x,y) holds. The task is to find some
solution y given 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 the 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.
2) Algebraic Computation and Proofs
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 the 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 of these areas there remain fundamental open problems.
This program is traditionally complemented by lectures of the
participants on their own work during Friday (there is no obligation
to deliver such a talk, though).
PARTICIPANTS: If you are interested to participate, please register
with Jan Krajicek (krajicek@math.cas.cz), 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.
For any additional information on the Fall School, please visit:
http://www.math.cas.cz/~krajicek/fall09.html