Tid: 20 mars 2014 kl 11.15-12.00.Seminarierummet 3733, Institutionen för matematik, KTH, Lindstedtsvägen 25, plan 7. Karta!
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.
|Sidansvarig: Filip Lindskog