cfry@watdcsu.waterloo.edu (C.Fry - Inst. Computer Research) (01/20/89)
ICR presents a colloquium on
Two Decades of Applied Kolmogorov Complexity
by
Dr. Paul M.B. Vitanyi
of
Centrum voor Wiskunde en Informatica
and
Department of Mathematics and Computer Science
Universiteit van Amsterdam
Abstract
This talk is an introduction to the main ideas of Kolmogorov com-
plexity and surveys the wealth of useful applications of this
elegant notion. Topics include notions of randomness; a version
of Godel's incompleteness theorem; lower bound arguments in for-
mal language theory, complexity of computation, and electronic
chips; Bayesian inference and a priori probability with applica-
tions ranging from foundational issues to the theory of learning
and inductive inference in Artificial Intelligence; resource-
bounded Kolmogorov complexity with applications ranging from NP-
completeness and the P versus NP question to cryptography. (We
will treat these subjects as far and in such multitude as feasi-
ble.) This is joint work with Ming Li, and is a selection from
the textbook "An Introduction to Kolmogorov Complexity and its
Applications" we are preparing.
DATE: Wednesday, January 25, 1989
TIME: 3:30 p.m.
PLACE: DC 1302
Everyone is welcome. Refreshments served.