CDI Type II: Pseudorandomness

这一提议旨在通过将两个并行进展的主要研究轨道结合在一起来改变数学和计算机科学的研究(尽管是通过不平凡的相互作用)。在数学中，许多领域(包括分析、数论、遍历理论和组合学)的研究对象都是这样一个问题：？一个(确定性)数学结构具有哪些类似随机的性质？？在计算机科学中，许多领域(包括网络理论、纠错、计算复杂性和去随机化)的研究对象都被这样一个问题抓住：我们能否确定性地、有效地设计具有特定随机性质的对象？PI将两个数学和CS轨迹分别视为理解相同的基本伪随机性现象及其与结构相互作用的分析和综合方法。计算机科学主要是数学的被动消费者，依赖于对结构的数学分析来建立期望的对象。我们建议通过使用随机性的计算观点来分析数学结构，将这种单向使用转变为完全成熟的合作。这一工具的初步应用，其中许多是由PI进行的，已经导致了对数学对象的新理解以及在将这些对象用作计算机科学构造基础方面的重大突破。这种交叉受精产生的最新突破的例子包括关于Cayley图中的扩张器的工作、和积定理中的抽取器、素数中的算术(和其他)级数以及Gowers？复杂性中的规范。许多人依赖于伪随机性这一概念计算工具，伪随机性是一类测试中的任何一种都无法区分随机对象和有问题的对象之间的区别。这个概念出现在密码学的复杂性理论方法中，但后来在计算机科学中得到了广泛的应用(例如，在对概率算法进行去随机化)。

This proposal aims to transform research in mathematics and computer science by bringing together two major research tracks which have been progressing in parallel (albeit with nontrivial interaction). In mathematics, the object of study in many areas (including analysis, number theory, ergodic theory and combinatorics) is captured by the question: ?What random-like properties does a (deterministic) mathematical structure have?? In computer science, the object of study in many areas (including network theory, error correction, computational complexity and derandomization) is captured by the question ?Can we deterministically and efficiently design objects with specific random-like properties?? The PIs view the two Math and CS tracks (respectively) as analytic and synthetic approaches for understanding the same fundamental pseudorandomness phenomena and its interaction with structure.Computer science has been mostly a passive consumer of mathematics, relying on the mathematical analysis of structures to build desireable objects. We propose to transform this one-way use to a full fledged collaboration, through the use of the computational view of randomness to analyze mathematical structures. Preliminary applications of this tool, many by the PIs, have already led to major breakthroughs both in new understanding of mathematical objects and in the use of these objects as the basis for constructions in computer science. Examples of recent breakthroughs resulting from this cross-fertilization include work on expanders in Cayley graphs, extractors from sum-product theorems, arithmetic (and other) progressions in primes, and the use of Gowers? norms in complexity. Many rely on the conceptual computational tool of pseudorandomness, the inability of any of a class of tests to tell the difference between a random object and the object in question. This notion arose in complexity-theoretic approaches to cryptography, but has since had wide applicability in computer science (e.g. in derandomizing probabilistic algorithms).