Towards measuring the information content of computing problems

The Faculty of Informatics is pleased to announce a seminar given by Juraj Hromkovic

DATE: Tuesday, November 19th, 2013
PLACE: USI Lugano Campus, room SI-015, Informatics building (Via G. Buffi 13)
TIME: 13.30

ABSTRACT:
Information is a fundamental notion in science but we do not have any reasonable exact definition of this term. Shannon, Kolmogorov and Chaitin tried to define the information content of finite objects and introduced in this way  very powerful research instruments. Shannon's entropy is measurable but it is definitely not a robust definition of the information content. Kolmogorov complexity is a robust definition of the information content but one cannot use it to measure the information content of concrete finite objects.
We think that there is no way to measure the information content of finite objects as well as it is no way to measure the computational complexity of particular problem instances. This is the motivation to introduce the information content of computing problems in online setting as a function of the problem instance size. Using this concept we discover the information content of several fundamental online problems and observe very different kinds of behaviours of the trade-offs between  the amount of information provided and the quality  of reachable solutions.

BIO:

• Since 2004: Professor of Computer Science, Swiss Federal Institute of Technology, Zürich
• 1997-03: Professor Chair of the Department of Computer Science I (Algorithms and Complexity) Aachen University RWTH, Germany
• 1994-97: Professor (Theory of Parallel Computing), Institute of Informatics, University of Kiel, Germany
• 1989-94: Visiting Professor Department of Computer Science and Mathematics, University of Paderborn, Germany
• 1989: Habilitation in Theoretical Cybernetics and Mathematical Informatics, Comenius University
• 1986: Promotion Dr. rer.nat., Comenius University, Bratislava

HOST: Prof. Stefan Wolf