|
Man has grappled with the notion of randomness for centuries.
In the past few decades, the computational viewpoint begun
to shed new light on this fundamental notion. This series
of lectures will explore, exemplify and explain some aspects
of this new understanding, focusing on the following themes.
The computational power of randomness: The use of randomness
in algorithms and cryptography has greatly enriched the collection
of tasks which can be performed efficiently. On the other
hand, the question to which extent is this power of randomness
real has lead to precise definitions of pseudorandomness and
derandomization, and to their fundamental relation to computational
difficulty.
Explicit construction of pseudorandom objects: Parallel strands
of research in computer science and mathematics pursued the
understanding of objects, like expander graphs and randomness
extractors, which have strong pseudorandom properties. Such
objects have numerous applications in both areas, which called
for their efficient, explicit constructions.
These topics are today a focus of great (often joint) research
activity of mathematicians and computer scientists, and we'll
survey both main accomplishments as well as main outstanding
challenges.
The lectures are aimed at a general mathematics and computer
science audience, and requires no special knowledge. We will
attempt to make the lectures relatively independent of each
other, so as to accommodate
people who can attend only a subset.
|
T