Corelab Seminar

Antonis Antonopoulos (NTUA)
Derandomization: A Basic Introduction

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.