Second Annual Kolmogorov Lecture

The speaker at the Second Annual Kolmogorov Lecture, held at Royal Holloway on 24th February 2004, was Professor Leonid Levin of Boston University. He presented a lecture entitled "Randomness and Non-determinism":

Professor Levin, one of the world’s foremost researchers in the field of Kolmogorov Complexity, works in the field of mathematical probability and the theory of computation, particularly in regard to randomness and complexity in computing. First introduced to Kolmogorov at the age of 15 during a school visit, he was later taught by Kolmogorov at Moscow University and was advised by him for his doctoral thesis. Professor Levin went on to become one of the originators of the theory of NP completeness (alongside S A Cook and R Karp). He was recently awarded an Outstanding Paper award by the Society of Applied and Industrial Mathematics for his work on Pseudorandom generators from one way functions.

Kolmogorov Lecture	L. Levin	The Reception

Synopsis: "Randomness and Non-determinism"

"In the decades since fundamental questions like P=?NP have been raised, we have not come much closer to answering them. Yet, we did learn one obscure but essential hint: a strange pattern of relationships between nondeterminism and randomness - another major deviation from deterministic computations.

I will give illustrations of these ideas: some simple, some powerful and ingenious to which many authors contributed. One example, foreshadowed by Andrei Kolmogorov, is the fundamental relationship between computer-generated randomness and hard nondeterministic problems (one-way functions). A converse example is a Monte-Carlo method for instant verification of proofs of any theorems or computations -- a quite general nondeterministic task."

Sponsors: