AF: Small: Challenges in Unconditional Pseudorandomness for Boolean Computation

AF：小：布尔计算无条件伪随机性的挑战

• 批准号: 1814788
• 负责人: Michael Forbes
• 金额: $ 35万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-01 至 2022-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814788&HistoricalAwards=false
• 关键词: AF; Small; Challenges; Unconditional; Pseudorandomness

The performance of modern computers can be measured on several axes, such as the time or memory consumed. Another axis is the amount of randomness used, as many common algorithms (such as opinion polls) use randomness as a key resource. However, true randomness (such as that derived from physical phenomena) can be a scarce resource, and as such significant research has explored how the use of randomness can be minimized while still efficiently solving key algorithmic problems. One prominent algorithmic challenge is to compute the volume of geometric objects. While this problem is simple in low dimensions, it is significantly more difficult in the higher number of dimensions often required for applications. While randomized algorithms have been developed for (approximately) computing volumes, comparable deterministic algorithms have yet to be developed. This project will study techniques for the design of such algorithms. It will also promote the study of pseudorandomness in general through course design, organization of workshops, and training of undergraduate and graduate students.In particular, this project will design pseudorandom generators, which are maps that stretch a short seed of (true) randomness to a longer output of pseudorandomness, where this output is indistinguishable from random (from the perspective of the relevant algorithm). The construction of suitable pseudorandom generators is a well-known avenue to the derandomization of algorithms. However, existing constructions of pseudorandom generators fall short of derandomization even for simple algorithmic problems. This project will study new paradigms for the construction of pseudorandom generators, especially for those which can derandomize algorithms for geometric problems such as (approximately) computing volumes. This study will be facilitated by combining existing tools, such as those from communication complexity and cryptographic pseudorandomness, in novel ways.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

现代计算机的性能可以通过多个轴来衡量，例如消耗的时间或内存。 另一个轴是使用的随机性数量，因为许多常见算法（例如民意调查）使用随机性作为关键资源。 然而，真正的随机性（例如源自物理现象的随机性）可能是一种稀缺资源，因此此类重要研究探索了如何最大限度地减少随机性的使用，同时仍然有效地解决关键算法问题。 一项突出的算法挑战是计算几何对象的体积。 虽然这个问题在低维中很简单，但在应用程序通常需要的更高维数中，这个问题要困难得多。 虽然已经针对（大约）计算量开发了随机算法，但尚未开发出类似的确定性算法。 该项目将研究此类算法的设计技术。 它还将通过课程设计、研讨会组织以及本科生和研究生培训来促进伪随机性的研究。特别是，该项目将设计伪随机生成器，这些生成器是将（真）随机性的短种子延伸到伪随机性的较长输出，该输出与随机输出无法区分（从相关算法的角度来看）。构建合适的伪随机生成器是算法去随机化的众所周知的途径。 然而，即使对于简单的算法问题，现有的伪随机生成器结构也无法实现去随机化。 该项目将研究构建伪随机生成器的新范式，特别是那些可以对几何问题（例如（近似）计算量）的算法进行去随机化的范式。 这项研究将以新颖的方式结合现有的工具，例如通信复杂性和加密伪随机性的工具。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Random Restrictions and PRGs for PTFs in Gaussian Space

高斯空间中 PTF 的随机限制和 PRG

• 发表时间: 2022-07
• 期刊: Leibniz international proceedings in informatics
• 作者: Kelley, Zander;Meka, Raghu
• 通讯作者: Meka, Raghu

Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals

理想、行列式和拉直：证明和使用多项式理想的下界

• DOI: 10.1145/3519935.3520025
• 发表时间: 2022-06
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Andrews, Robert;Forbes, Michael A.
• 通讯作者: Forbes, Michael A.

An improved derandomization of the switching lemma

改进的切换引理去随机化

• DOI: 10.1145/3406325.3451054
• 发表时间: 2021-06
• 期刊: STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Kelley; Zander
• 通讯作者: Zander

Pseudorandom Generators for Read-Once Branching Programs, in Any Order

用于以任意顺序读取一次的分支程序的伪随机生成器

• DOI: 10.1109/focs.2018.00093
• 发表时间: 2018-10
• 期刊: 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018
• 作者: Forbes, Michael A.;Kelley, Zander
• 通讯作者: Kelley, Zander

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

即使在量子世界中，空间隔离也意味着零知识

• DOI: 10.1109/focs.2018.00077
• 发表时间: 2018-10
• 期刊: 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018
• 作者: Chiesa, Alessandro;Forbes, Michael A.;Gur, Tom;Spooner, Nicholas
• 通讯作者: Spooner, Nicholas