Randomness Extraction and Applications

随机性提取及应用

• 批准号: 0634811
• 负责人: David Zuckerman
• 金额: $ 33万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-10-01 至 2010-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0634811&HistoricalAwards=false
• 关键词: Randomness; Extraction; 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.

项目摘要：随机性的提取及应用随机性在计算中非常有用。然而，在实践中，获得真正的随机数是昂贵的或不可能的。所以科学家们使用“伪随机发生器"。“然而，这些有时会失败，所以科学家使用它们来运行模拟可能会在不知情的情况下得到错误的答案。这项研究的重点是随机性提取器：从低质量随机源中提取高质量随机性的有效算法。这些提取器已经被证明不仅对他们的既定目标有用，而且对密码学，编码理论和网络构造等不同领域都很有用。更具体地说，这项研究涉及为尽可能一般的一类随机源寻找随机性提取器。要研究的源包括独立源、小空间源、仿射源以及新的源。不可能为完全通用的源构建随机性提取器;然而，通过添加一个小的随机种子是可能的。本研究包括改进种子长度和输出以接近它们的最优值。最后，本研究进一步发展了几个应用领域：伪随机性、密码学、逼近困难和随机选择。