Randomness Extraction and Applications

点击翻译按钮获取中文摘要

Project Abstract: Randomness Extraction and ApplicationsRandomness is extremely useful in computation. In practice, however, it is expensive or impossibleto 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.