17-20 February 2010, Workshop on "Logical Approaches to Barriers in Computing and Complexity", Greifswald, Germany

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.

For more information, see http://www.cs.swan.ac.uk/greifswald2010/