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.

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

项目成果

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

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

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

An improved derandomization of the switching lemma

改进的切换引理去随机化

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

Random Restrictions and PRGs for PTFs in Gaussian Space

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

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

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

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

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

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

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