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.