AF: Small: Challenges in Unconditional Pseudorandomness for Boolean Computation

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

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.