Corelab Seminar
2010-2011
Antonis Antonopoulos (NTUA)
Derandomization: A Basic Introduction
Abstract.
During the past years, randomization has offered a great comfort in Computer Science,
by providing efficient algorithms for many computational problems.
The class BPP has almost replaced P as the class of efficiently solvable problems.
This progress also raised a question: The simplification given to our
computations by using a random ”coin toss” is inherent or circumstantial?
In other words, randomization provides a (non-trivial) computational boost-
up, or it’s just a design comfort, and we can finally remove it?
Recent advances have proven that it is possible, under some plausible complexity
assumptions (if certain combinatorial objects of "high" non-uniform complexity exist),
to replace a BPP randomized algorithm with a deterministic one (i.e., to derandomize),
only with polynomial loss of efficiency. Today, there are many researchers who believe
that finally BPP = P. In this lecture we will summarize the most significant results,
and we will discuss the importance of such collapses in our computational models.