[FOM] 2nd Call for Papers: Greifswald 2010

Arnold Beckmann A.Beckmann at swansea.ac.uk
Sat Aug 15 04:09:25 EDT 2009


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

                    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:

Submission of extended abstracts: 15 October 2009
Notification of authors: 1 December 2009
Deadline for final revisions: 5 Januar 2010
Workshop: 17-20 February 2010

We have funds to offer financial support to authors of accepted
papers.  In individual cases refunds can range up to full
reimbursement of travel and accommodation costs.  Further detail will
be announced on the webpage.

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

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

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)

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

More information about the FOM mailing list