44th Multi-dimension Seminar
Information distance
Sebastiaan A. Terwijn

Department of Mathematics
Radboud University Nijmegen

2012-11-09 (Friday), 15:15-16:45

K Lecture room 1・2

Information distance is a notion from theoretical computer science that was introduced by Bennett, Gacs, Li, Vitanyi, and Zurek in 1998. Information distance, and derived notions such as normalized information distance, have proven useful in a number of ways. Besides being interesting for theoretical reasons, they have led to a number of surprising practical applications, of which we will show some examples. In this talk we will discuss the complexity of the information distance, and related results about time-bounded Kolmogorov complexity.

担当者

Norbert Preining