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