Institute for Logic, Language and Computation
CiE-CS: CiE 2009
CiE 2009: Mathematical Theory and Computational Practice.
Heidelberg, Germany. 19-24 July 2009

Organizers: K. Ambos-Spies, B. Cooper, B. Löwe, W. Merkle

Programme Committee:

Klaus Ambos-Spies (Heidelberg, co-chair) Giorgio Ausiello (Roma) Andrej Bauer (Ljubljana)
Arnold Beckmann (Swansea) Olivier Bournez (Nancy) Vasco Brattka (Cape Town)
Barry Cooper (Leeds) Anuj Dawar (Cambridge) Jacques Duparc (Lausanne)
Pascal Hitzler (Karlsruhe) Rosalie Iemhoff (Utrecht) Margarita Korovina (Siegen / Novosibirsk)
Hannes Leitgeb (Bristol) Daniel Leivant (Bloomington IN) Benedikt Löwe (Amsterdam)
Giancarlo Mauri (Milano) Elvira Mayordomo (Zaragoza) Wolfgang Merkle (Heidelberg, co-chair)
Andrei Morozov (Novosibirsk) Dag Normann (Oslo) Isabel Oitavem (Lisboa)
Luke Ong (Oxford) Martin Otto (Darmstadt) Prakash Panangaden (Montréal QC)
Ivan Soskov (Sofia) Viggo Stoltenberg-Hansen (Uppsala) Peter van Emde Boas (Amsterdam)
Jan van Leeuwen (Utrecht) Philip Welch (Bristol) Richard Zach (Calgary AB)

Special Sessions
  • Algorithmic Randomness. Organizers: Elvira Mayordomo (Zaragoza) and Wolfgang Merkle (Heidelberg)
  • Computational Model Theory. Organizers: Julia F. Knight (Notre Dame) and Andrei Morozov (Novosibirsk)
  • Computation in Biological Systems: Theory and Practice. Organizers: Alessandra Carbone (Paris) and Erzsébet Csuhaj-Varjú (Budapest)
  • Optimization and Approximation. Organizers: Gerhard Reinelt (Heidelberg)
  • Philosophical and Mathematical Aspects of Hypercomputation. Organizers: James Ladyman (Bristol) and Philip Welch (Bristol)
  • Relative Computability. Organizers: Alexandra A. Soskova (Sofia)
General Description:

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.