| Abstract: |
In combinatorics, the probabilistic method is a very
powerful tool to prove the existence of combinatorial objects with
interesting and useful properties. Explicit constructions of objects
with such properties are often very difficult, or unknown. In computer
science, probabilistic algorithms are sometimes simpler and more
efficient than the best known deterministic algorithms for the same
problem.
Despite this evidence for the power of random
choices, the computational theory of pseudorandomness shows that,
under certain complexity-theoretic assumptions, every probabilistic
algorithm has an efficient deterministic simulation and a large class
of applications of the the probabilistic method can be converted into
explicit constructions.
In this survey talk we describe connections
between the conditional ``derandomization'' results of the
computational theory of pseudorandomness and unconditional explicit
constructions of certain combinatorial objects such as
error-correcting codes and ``randomness extractors.''
|
