17-20 February 2010
Greifswald, Germany
**********************************************************************
FIRST CALL FOR PAPERS
The "Deutsche Vereinigung fuer Mathematische Logik und fuer Grundlagen
der Exakten Wissenschaften" (DVMLG), the "Polskie Towarzystwo Logiki
i Filozofii Nauki" (PTLiFN), the "Association Computability in Europe"
(ACiE) and the "European Association for Computer Science Logic"
(EACSL) jointly organize a workshop on
Logical Approaches to Barriers in Computing and Complexity
http://www.cs.swan.ac.uk/greifswald2010/
Greifswald, 17-20 February 2010
The workshop is sponsored by the Stiftung Alfried Krupp Kolleg
Greifswald, and takes place at the Alfried Krupp Wissenschaftskolleg
in Greifswald, Germany:
http://www.wiko-greifswald.de/events/cal/article/6/logical-approaches.html
IMPORTANT DATES:
Submission of extended abstracts: 15 September 2009
Notification of authors: 1 November 2009
Deadline for final revisions: 1 December 2009
Workshop: 17-20 February 2010
Computability theory and complexity theory have their origins
in logic. Famous names such as Goedel, Turing, Cook, and
Kolmogorov connect these areas of computer science to foundations
of mathematics. The fundamental goal of this area is to understand
the limits of computability (that is analysing which problems can
be solved on nowadays and future computers in principle) and
effective computability (that is understanding the class of
problems which can be solved quickly and with restricted
resources) where the most famous open problem is the P=NP-problem.
Logic provides a multifarious toolbox of techniques to analyse
questions like this, some of which promise to provide a deep
insight in the structure of limit of computation.
In our workshop, we shall focus on the following aspects: logical
descriptions of complexity (e.g., descriptive complexity, bounded
arithmetic), complexity classes of abstract, algebraic and
infinite structures, barriers in proving complexity results, and
Kolmogorov complexity and randomness.
Some of these aspects are particularly timely: recently, research
in these areas became more intense. Part of this is the new
conference series CiE (run by the Association for Computability
in Europe) whose range of interests includes those of our
workshop, creating an important focus on the emerging topics of
the field. This workshop is intended as a research-oriented
follow-up to the CiE conferences, allowing researchers ample time
for discussions and joint work.
KEYNOTE SPEAKERS:
Alessandra Carbone (Paris, France), Lance Fortnow (Evanston, IL,
U.S.A.), Erich Graedel (Aachen, Germany), Pascal Koiran (Lyon,
France), Leszek Kolodziejczyk (Warsaw, Poland), Antonina Kolokolova
(St.John's, NL, Canada).
SPECIAL SESSION:
There will be a special session on "Complexity in Arbitrary
Structures" organised by Christine Gassner (Greifswald, Germany)
and Martin Ziegler (Paderborn, Germany).
Details about the special session will be published on our
website in due course.
Contributed talks will be selected from submissions received
by the PROGRAM COMMITTEE consisting of:
* Zofia Adamowicz (Warsaw, Poland)
* Franz Baader (Dresden, Germany)
* Arnold Beckmann (chair; Swansea, Wales)
* Sam Buss (La Jolla CA, U.S.A.)
* Manfred Droste (Leipzig, Germany)
* Christine Gassner (Greifswald, Germany)
* Peter Koepke (Bonn, Germany)
* Benedikt Loewe (Amsterdam, The Netherlands)
* Johann Makowsky (Haifa, Israel)
* Elvira Mayordomo (Zaragoza, Spain)
* Damian Niwinski (Warsaw, Poland)
* Wolfgang Thomas (Aachen, Germany)
* Martin Ziegler (Paderborn, Germany)
SUBMISSIONS:
The Programme Committee cordially invites all researchers in the
area of the workshop to submit their extended abstracts
(in PDF-format, at most 4 pages) for presentation at the workshop.
Further details about submission can be found on our website
http://www.cs.swan.ac.uk/greifswald2010/
Accepted abstracts will be printed in an abstract booklet which
will be distributed to the participants of the workshop.
We emphatically encourage submissions by female authors, as women
are underrepresented in mathematics and computer science.
Submission of abstracts of published and presented work is also
possible, since the abstract booklet is non-archival.
Quality and quantity of submissions permitting, we plan to
invite the authors of unpublished papers to submit a full version
to a post-proceedings volume after the workshop.