17-20 Feb 2010
Greifswald, Germany
**********************************************************************
FINAL 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 the Deutsche Forschungsgemeinschaft (DFG), 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: 7 November 2009
Notification of authors: 15 December 2009
Deadline for final revisions: 5 Januar 2010
Workshop: 17-20 February 2010
FINANCIAL SUPPORT:
The local hotel costs of speakers of accepted talks will be covered.
In addition to that, we are able to offer partial reimbursement of the
travel expenses to speakers of accepted talks. In exeptional cases
full reimbursement is possible.
DESCRIPTION:
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 efficient
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:
The workshop features a special session on "Complexity in Arbitrary
Structures" organised by Christine Gassner (Greifswald, Germany) and
Martin Ziegler (Paderborn, Germany). Invited speakers of the
special session are
* Bruno Poizat (Villeurbanne, France) (KEYNOTE)
* Olivier Bournez (Palaiseau, France)
* Guenter Hotz (Saarbruecken, Germany)
* Klaus Meer (Cottbus, Germany)
* Monika Seisenberger (Swansea, Wales)
* Klaus Weihrauch (Hagen, Germany)
* Chee Yap (New York, USA)
* Thierry Zell (Hickory, NC, USA)
Further details can be found at the special session website
http://www.math-inf.uni-greifswald.de/biomathematik/gassner/SpecialSession.htm
Contributed talks will be selected by the Programme Committee from
received submissions. The PROGRAM COMMITTEE consists 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.