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的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

项目成果

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