Presidential Young Investigator Award: Randomness and Parallelism in the Solution of Computational Problems

总统青年研究员奖：计算问题解决方案中的随机性和并行性

• 批准号: 8658143
• 负责人: Umesh Vazirani
• 金额: $ 1.63万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-08-01 至 1988-05-25
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8658143&HistoricalAwards=false
• 关键词: Presidential; Young; Investigator; Award; Randomness

The number of solutions of a computational problem and their distribution have fundamental implications upon its computational efficiency. When the solutions are symmetrically located an algorithm that cannot distinguish between two solutions cannot (by symmetry) converge to either answer. Randomization is often effective precisely because it can break such symmetries. In joint work, the PI has shown that an adversary source of randomness is sufficient to break symmetries (thus showing RP = SRP). What is novel about this approach is that identifying symmetry breaking as the essential task of randomization allows one to ask more precisely how much randomness is really needed for efficient computation. Two related questions now being addressed are: What are necessary and sufficient conditions for a source of randomness to be a universal symmetry breaker? How many random bits are necessary? A pseudo-random number generator is quasi-perfect if its output satisfies universal symmetry breaking properties. The PI has recently proposed a simple and efficient pseudo-random number generator. An attempt is now being made to settle the associated conjecture that this generator is quasi-perfect. Massively parallel computation provides another context where the difficulty can lie in the task of selecting one solution among many. In joint work the PI has given a general scheme for isolating one solution in parallel (obtaining a parallel algorithm for the maximum matching problem). Further applications of this isolating scheme are now being explored. The PI has been judged to be an outstanding computer scientist by the Presidential Young Investigators panel.

一个计算问题的解的个数及其 分布 对它的计算效率有根本的影响。 当 的 解决方案是对称定位的算法，不能 区分 两个解之间不能（通过对称性）收敛到任何一个答案。 随机化往往是有效的，因为它可以打破这种 对称性 在联合工作中，PI已经表明， 随机性足以打破对称性（因此显示RP = SRP）。 这种方法的新颖之处在于， 因为随机化的基本任务允许人们更精确地询问 有效计算需要多少随机性。 两 现在正在讨论的相关问题是：什么是必要的， 随机性源是泛随机性的充分条件 对称破坏者？ 需要多少随机位？ 伪随机 如果一个数生成器的输出满足泛 对称性破缺 PI最近提出了一个简单的 和高效的伪随机数生成器。 目前， 为了解决相关的猜想，这台发电机是 准完美 大规模并行计算提供了另一种环境， 困难可能在于从许多解决方案中选择一个解决方案的任务。 在联合工作中，PI给出了一个隔离一个 并行解决方案（获得最大值的并行算法 匹配问题）。 此隔离方案的进一步应用 现在正在探索。 PI被评为杰出的计算机科学家， 总统青年调查员小组