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).