1st Call for Papers: Greifswald 2010

[Arnold Beckmann]

[Apologies for multiple copies]

**********************************************************************
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.