AF: Small: Randomness in Computation - New Directions and Techniques

AF：小：计算中的随机性 - 新方向和技术

• 批准号: 1217416
• 负责人: Zeev Dvir
• 金额: $ 44.7万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217416&HistoricalAwards=false
• 关键词: AF; Small; Randomness; Computation; New

The overarching goal of this project is to improve our understanding of the power of randomness in designing efficient algorithms, constructing graphs that behave like "random" graphs, and in proving certain mathematical results. One of the basic questions in randomness is that of obtaining "pure" random bits from real-world sources of randomness. Procedures developed for this purpose are called extractors and have found many applications, some of which are completely unrelated to their original motivation. A recent line of research (by the PI and others) has resulted in new techniques, especially algebraic, being introduced to this area. This resulted in new constructions of extractors that go beyond previous barriers. One of the main goals of this project is to further study these techniques and obtain better constructions of extractors producing more random bits of higher quality than known before.Another central question studied in this project is Polynomial Identity Testing (PIT) - testing whether a given arithmetic expression is an identity or not. This can be done efficiently using randomness but a deterministic algorithm is not known. The importance of finding deterministic algorithms for this problem (or even to special cases of it) is of major importance and attracted a lot of attention (including work by the PI with co-authors). A third major goal of this project is to obtain deterministic PIT algorithms for classes of circuits for which only randomized algorithms are known. This is tightly related to proving new computational hardness results, being a yet another target for this project.This project aims at expanding our understanding of randomness as a computational resource while developing new and transformative mathematical techniques and concepts for attacking long-standing problems in this area. Progress on could lead to new practically useful insights into algorithms, coding theory and cryptography among others. The PI will be involved in organizing seminars, reading groups and writing survey articles aimed at disseminating knowledge gained during the proposed research to the wider academic community. In addition, the PI will give public talks, including to high school students, and those aimed at a non-technical audience.

这个项目的首要目标是提高我们对随机性在设计有效算法、构建表现得像“随机”图的图以及证明某些数学结果方面的能力的理解。 随机性的基本问题之一是从真实世界的随机性来源中获得“纯”随机位。 为此目的开发的程序被称为提取器，并已发现许多应用程序，其中一些与其原始动机完全无关。 最近的一系列研究（由PI和其他人）导致了新的技术，特别是代数，被引入到这个领域。 这导致了新的提取器的建设，超越了以前的障碍。 该项目的主要目标之一是进一步研究这些技术，并获得更好的提取器的构造，产生比以前更高质量的更多随机比特。该项目研究的另一个中心问题是多项式恒等式测试（PIT）-测试给定的算术表达式是否是恒等式。 这可以使用随机性有效地完成，但不知道确定性算法。 为这个问题（甚至是它的特殊情况）找到确定性算法的重要性是非常重要的，并吸引了大量的关注（包括PI与合著者的工作）。 这个项目的第三个主要目标是获得确定性的PIT算法的电路类，只有随机算法是已知的。 这与证明新的计算硬度结果密切相关，是该项目的另一个目标。该项目旨在扩大我们对随机性作为计算资源的理解，同时开发新的和变革性的数学技术和概念，以解决该领域长期存在的问题。 这方面的进展可能会导致对算法，编码理论和密码学等的新的实用见解。 PI将参与组织研讨会、阅读小组和撰写调查文章，旨在向更广泛的学术界传播拟议研究期间获得的知识。 此外，PI将进行公开演讲，包括高中生，以及针对非技术受众的演讲。