Elyot Grant is giving a talk on Tuesday July 20th at 4:30pm in MC2066. The information follows below:
Title: The Incompressibility Method
Abstract:
Heapsort. It runs in $\Theta(n \log n)$ time in the worst case, and in $O(n)$
time in the best case. Do you think that heapsort runs faster than $O(n \log n)$
time on average? Could it be possible that on most inputs, heapsort runs in
$O(n)$ time, running more slowly only on a small fraction of inputs?
Most students would say no. It "feels" intuitively obvious that heapsort should
take the full $n \log n$ steps on most inputs. However, proving this rigourously
with probabilistic arguments turns out to be very difficult. Average case
analysis of algorithms is one of those icky subjects that most students don't
want to touch with a ten foot pole; why should it be so difficult if it is so
intuitively obvious?
In this talk, we shall explore the incompressibility method---an interesting and
extremely powerful framework for determining the average-case runtime of
algorithms. Within the right background knowledge, the heapsort question can be
answered with an elegant 3-line proof.
The crucial fact is that an overwhelmingly large fraction of randomly generated
objects are incompressible. We can show that the inputs to heapsort that run
quickly correspond to inputs that can be compressed, thereby proving that
heapsort can't run quickly on average. Of course, "compressible" is something
that must be rigourously defined, and for this we turn to the fascinating theory
of Kolmogorov complexity.
In this talk, we'll briefly discuss the proof of the incompressibility theorem
and then see a number of applications. We won't dwell too much on gruesome
mathemtical details. No specific background is required, but knowledge of some
of the topics in CS240 will be helpful in understanding some of the
applications.