CDI Type II: Pseudorandomness

CDI II 型：伪随机性

• 批准号: 0835373
• 负责人: Avi Wigderson
• 金额: $ 175万
• 依托单位: Institute For Advanced Study
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-10-01 至 2013-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0835373&HistoricalAwards=false
• 关键词: CDI; Type; II; Pseudorandomness

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

该提案旨在通过将并行进展的两个主要研究方向结合在一起（尽管存在不平凡的相互作用）来改变数学和计算机科学的研究。在数学中，许多领域（包括分析、数论、遍历理论和组合学）的研究对象都是通过以下问题来捕获的：“（确定性）数学结构具有哪些类似随机的属性？”在计算机科学中，许多领域（包括网络理论、纠错、计算复杂性和去随机化）的研究对象都集中在“我们能否确定性且有效地设计具有特定类随机属性的对象？”这一问题上。 PI 将数学和计算机科学这两个方向（分别）视为分析和综合方法，用于理解相同的基本伪随机现象及其与结构的相互作用。计算机科学基本上是数学的被动消费者，依赖于结构的数学分析来构建想要的物体。我们建议通过使用随机性的计算视图来分析数学结构，将这种单向使用转变为全面的协作。该工具的初步应用（许多是由 PI 完成的）已经在对数学对象的新理解以及使用这些对象作为计算机科学构造的基础方面带来了重大突破。这种交叉融合带来的最新突破的例子包括凯莱图中的扩展器、和积定理的提取器、素数的算术（和其他）级数以及高尔斯？复杂性规范。许多依赖于伪随机性的概念计算工具，任何一类测试都无法区分随机对象和相关对象之间的区别。这个概念出现在密码学的复杂性理论方法中，但此后在计算机科学中具有广泛的适用性（例如，在去随机化概率算法中）。