Tid: 20 mars 2014 kl 11.15-12.00.

Föredragshållare: Osamu Watanabe, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology

Titel: Normalized Compression Distance and its Theoretical Analysis

Abstract Normalized compression distance (NCD in short) has been proposed by M. Li et al. as a universal way to measure similarity between two given strings based on the theory of Kolmogorov complexity. Although many interesting and appealing applications of using NCD have been reported, its theoretical justification has not been given. In this talk, I would like to explain some approach for analyzing NCD theoretically and discuss some possible future research for studying NCD and its property mathematically. Technically, we show some preliminary theoretical analysis on NCD with a compression method used in bzip.

(This is a joint work with Toshihiko Yusa.)

Brief bio of speaker:

Osamu Watanabe is a professor at Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Japan. He received B.Sc. and M.Sc. in Information Science and Dr.Eng. in Computer Science from Tokyo Institute of Technology in 1980, 1982. and 1987 respectively. He has been working in the field of theory of computation, in particular, computational complexity theory and design and analysis of algorithms.

Till seminarielistan
To the list of seminars