Osamu Watanabe: Normalized Compression Distance and its Theoretical Analysis
Time: Thu 2014-03-20 11.15 - 12.00
Location: Room 3733, Lindstedtsvägen 25, 7th floor, Department of mathematics, KTH
Participating: Osamu Watanabe, Tokyo Institute of Technology
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.