Title: Pseudorandomness and combinatorial constructions
Speaker: Luca Trevisan

The probabilistic method in combinatorics and
the use of randomness in computer science are
very powerful tools. In some cases, it has
taken decades (or it is still an open question)
to come up with explicit constructions of objects
whose existence easily follows from the probabilistic
method, or to devise fully deterministic algorithms
as efficient as certain randomized ones.

The computational theory of pseudorandomness, however,
shows that, if certain complexity-theoretic
conjectures are true, then all randomized algorithms have a fully
deterministic analog of comparable efficiency and
a certain class of probabilistic existence proofs
can be made constructive. Such conditional results
are built upon, and  have contributed to, unconditional
results on the construction of extremal combinatorial
objects such as error-correcting codes, expander
graphs, randomness extractors, etc.

In this overview talk I will describe some of the
main ideas and results in this theory, such as
the definition of a distribution being 'pseudorandom'
if it passes all efficiently computable statistical
tests of randomness, and the connection between
computational complexity and pseudorandomness.