#### Milestone Year

### 2003

#### Purifying randomness

While many algorithms and protocols use randomness in an inherent manner,
the sources of randomness available to computations are imperfect.
It is thus desirable to have efficient procedures that extract
almost perfect randomness (i.e., a sequence of almost unbiased coin tosses)
out of any source that posses a minimal amount of randomness.
In other words, these procedures, called randomness extractors,
transform sources of poor-quality randomness
into sources of high-quality randomness.

WIS scientists have contributed to the study of this general problem,
both in initiating the study of various models of poor-quality sources
of randomness and in constructing randomness extractors for some
of these models.
For example, in the mid 1980s two models were proposed:
The block-source model and the bit-fixing model.
A block-source outputs a sequence of blocks of fixed length
such that each block is not totally determined by the prior blocks,
whereas a bit-fixing source outputs a sequence of bits in which
some bit locations are assigned at random and the other are fixed.

In 2003, a WIS scientist constructed randomness extractors that invest
a minimal amount of randomness, called a seed, to extract almost all
of the randomness from general sources of poor-quality randomness.
An illustrative analogy is that of oil refinery,
where some energy is invested to process crude oil
such that the refined oil yields much more energy than that invested.
This was the first explicit construction optimal up to a constant
in both the length of the seed and the amount of randomness extracted.