Randomness Extraction and Applications

University Of Texas At Austin, Austin TX

Investigators

Abstract

Project Abstract: Randomness Extraction and Applications Randomness is extremely useful in computation. In practice, however, it is expensive or impossible to get truly random numbers. so scientists use "pseudorandom generators." However, these sometimes fail, so scientists using them to run simulations may get the wrong answers without knowing it. This research focuses on randomness extractors: efficient algorithms which extract high-quality randomness from a low-quality random source. Such extractors have proven useful not only for their stated goal, but for areas as diverse as cryptography, coding theory, and network constructions. More specifically, this research involves finding randomness extractors for as general a class of random sources as possible. Sources to be investigated include independent sources, small space sources, affine sources, as well as new sources. It is impossible to construct randomness extractors for completely general sources; however, it is possible with the addition of a small random seed. This research includes improving the length of the seed and the output to close to their optimal values. Finally, this research further develops several application areas: pseudorandomness, cryptography, hardness of approximation, and random selection.