CiE-CS: CiE 2009
Computability in Europe
CiE 2009: Mathematical Theory and Computational Practice.
Heidelberg, Germany. 19-24 July 2009
Organizers: K. Ambos-Spies, B. Cooper, B. Löwe, W. Merkle
The scope of CiE 2009 encompasses theoretical and practical issues in computer science, with a focus on the interplay between these types of issues. In particular submissions are solicited that derive such interactions that relate to recent developments in mathematical theory and computational practice.
Research in computer science comprises a wide spectrum that ranges from the construction of real-world applications to highly theoretical questions. For example, on the more practical side there is the quest for efficient algorithms that solve practically relevant problems while on the more theoretical side one investigates the boundaries of what can be computed efficiently or can be computed at all. In many areas there is considerable interplay between practical and theoretical questions and in particular in the area of decision and optimization algorithms this interplay has been vivid and fruitful over the last half century. In the early days, the inability to find efficient algorithms for certain practical problems led to the theory of NP-completeness, which in turn provided guidance for the practitioner. More recently, the PCP-theorem, one of the major achievements in theoretical computer science of the last decade, yielded limits on the approximability of a considerable number of practically relevant optimization problems. It is to be expected that based on recent developments in computer science similarly tight relations between mathematical theory and computational practice will be established, e.g., for theoretical results in effective analysis or effective randomness and for practical questions that relate to distributed computing and the internet in general.