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

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

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.