Title: Average-case analysis, Shellsort, and Kolmogorov complexity
Speaker: Ming Li

Visiting Professor
Computer Science Department
City University of Hong Kong
and
Canada Research Chair in Bioinformatics
School of Computer Science
University of Waterloo


Date: Friday, April 15, 2005
Time 11-12
Venue: Room 3464, HKUST


Abstract

Analyzing the average-case complexity of an algorithm or a program is 
important in almost all computer science research areas, but
it is very difficult. 

My goal is to promote a powerful and routine 
methodology of analyzing average-case
complexity of algorithms. This is the incompressibility 
method, using Kolmogorov complexity. 
We will demonstrate the methodology by some examples
such as the average-case analysis of Shellsort.

=======================================================
Joint work with Tao Jiang and Paul Vitanyi. Some background 
on Kolmogorov complexity can be found in
"An introduction to Kolmogorov complexity and its applications"
by Ming Li and Paul Vitanyi, Springer-Verlag, 1997, 2n Edition;