### 10^{th} Estonian Winter School in Computer Science (EWSCS)

X Eesti Arvutiteaduse Talvekool

#### Palmse, Estonia, February 27 - March 4, 2005

### 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

URL: http://www.daimi.au.dk/~bromille/