Thursday, May 01, 2003
History's Loss/Mathematics' Gain
Some excitement at Schloss Dagstuhl this week. Localized high winds
tore the metal plating off the roof of much of the new building
Wednesday evening. Much of that roof sits in the courtyard--quite a
sight. The good news is no one was injured and property damage,
besides the roof, was minimal. A few of us had to switch rooms but the
workshop goes on.
Let me finish off this centennial week with a story of Kolmogorov that
I have heard from different sources so some variation of this story is
likely true. Kolmogorov initially wanted to be an historian. He looked
at the question as to whether taxes in Russia in the middle-ages were
collected at the house level or at the village level. He analyzed tax
data and showed that that data had a much simpler description if taxes
were collected at the village level. (You can see the seeds of
Kolmogorov complexity here). He presented these results to the history
faculty to great applause. Asking them whether he could publish such a
paper he was told, "You only have one proof. You cannot publish in a
history journal without at least two more proofs of your hypothesis."
And so Kolmogorov left history for a field where one proof suffices.
Wednesday, April 30, 2003
The Power of Random Strings
Let R be the set of random strings, the x such that C(x)≥|x|. There
are various theorems that many such x must exist at every length. What
is the power of R?
R is co-r.e. as one can enumerate small programs to generate the
strings x such that C(x)<|x|. One can also reduce the halting
problem to R: Suppose we want to know whether a program p halts on
blank tape. Let n=|p|. Let t be the number of steps to enumerate all
of the strings in R of length 2n. We know when we have enumerated them
all by using R. Then if p halts it will halt within t steps. Otherwise
let s>t be the number of steps p needs to halt. We can run the
enumeration of strings in R of length 2n for s steps. Let x be the
lexicographically least string of length 2n not enumerated. We have
C(x)≤|p|+O(1) since we need only p to describe this process. But
since |p|<2n=|x| this contradicts the fact that we had enumerated
all the nonrandom strings.
In this workshop Eric Allender talked about his
work with various colleagues looking at what one can get with
polynomial-time reductions to random strings. The reduction time above
is not bounded by any recursive function. For example they can show
any language in PSPACE polynomial-time reduces to R and any language
in EXP reduces to R via polynomial-size circuits, as well as many
results on different notions of random strings. They use various
complexity tools like pseudorandom generators and interactive
proof systems in their proofs.
Tuesday, April 29, 2003
More on Kolmogorov Complexity
There is a great Dilbert cartoon explaining the need for Kolmogorov
complexity. Because of copyright issues, I won't put it here (but you
might find it at the bottom of Sophie Laplante's web page). Reading the cartoon
you might find it funny because not all strings seem equally random
even if they are equally likely. Kolmogorov formalized this idea by
measuring the randomness of a string x, denoted C(x), by the smallest
program that generates x.
At this Dagstuhl workshop there are many talk on a number of
variations of Kolmogorov complexity. John Tromp had a nice
presentation on the basic notion. He showed, among other things, that
for any x you can find a constant length y such that C(xy)>C(x). This
seems obvious but it is pretty tricky tor prove. Tromp's proof works
by defining a new C-based measure on strings and using that to show
that any string x has a small number of programs generating x that
have length close to C(x) and using that fact to get his result. He
doesn't have a write-up yet, but I'll keep a lookout for it.
Sunday, April 27, 2003
Andrei Kolmogorov was born exactly hundred years ago last Friday the
25th. Kolmogorov made major contributions to "every mathematical
area except number theory" as many a Russian have put it. He has
directly affected my research through his algorithmic study of
randomness, an area we now call Kolmogorov complexity.
To celebrate the centennial, I'm back in Dagstuhl for a workshop on
Kolmogorov complexity after a brief stop in Heidelberg. Most of the
best researchers in the area are here including many Russians. It
should be an exciting week all around and during the week I will post
some of the interesting work that I hear about.
For a background on Kolmogorov complexity, here are some lecture notes
from a short course I gave. For an in-depth study, I cannot recommend
enough the Kolmogorov Complexity book of Li and Vitanyi.