Average-Case Analysis Using Kolmogorov Complexity

This expository paper demonstrates how to use Kolmogorov complexity to do the average-case analysis via four examples, and exhibits a surprising property of the celebrated associated universal distribution. The four examples are: average case analysis of Heapsort [17, 15], average nni-distance between two binary rooted leave-labeled trees [20], compact routing in computer networks [3], average-case analysis of an adder algorithm [4]. The property is that the average-case complexity of any algorithm whatsoever equals its worst-case complexity if the inputs are distributed according to the Universal Distribution [14]. We provide the proofs for the latter three items. 1 Introduction Kolmogorov complexity has been very successfully applied to obtain lower bounds solving many long-standing open questions. See [15] for details. A much less wellknown fact is that Kolmogorov complexity is also a powerful tool for average-case analysis of algorithms. The purpose of this expository paper is to ..