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.