10th Estonian Winter School in Computer Science (EWSCS)
X Eesti Arvutiteaduse Talvekool
Palmse, Estonia, February 27 - March 4, 2005
under the auspices of European Educational Forum
Peter Bro Miltersen
Dept. of Computer Science
University of Aarhus
Denmark
Universal Methods for Derandomization
Abstract
In these lectures, we consider the following related questions:
- How can we amplify the success probability of a randomized algorithm without using too many extra random bits?
- How can we run randomized algorithm using an imperfect random source?
- How can we turn our randomized algorithm into a deterministic one?
One can consider these questions both for specific randomized algorithms (using details of the analysis of the algorithms) and for arbitrary ones (i.e., without making assumption about the way the algorithms use the randomness). We shall deal with the latter kind of universal methods for derandomization. In the last decade, significant progress has been made in finding optimal universal methods. We shall give an introduction to these results.
Course materials
- P. B. Miltersen. Universal methods for derandomization. Lecture 1: Randomness in computation: five examples and a universal task. Slides. [pdf]
- P. B. Miltersen. Universal methods for derandomization. Lecture 2: Disperses and extractors. Slides. [pdf]
- P. B. Miltersen. Universal methods for derandomization. Lecture 3: Hitting set and pseudorandom generators. Slides. [pdf]
Background material
- P. B. Miltersen. Derandomizing complexity classes. Ch. 19 in S. Rajasekaran, P. M. Pardalos, J. H. Reif, J. D. Rolim, eds., Handbook of Randomized Computing, vols. 1-2, v. 9 of Combinatorial Optimization. Kluwer Academic Publishers, 2001.
About the Lecturer