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将Math和CS这两个方向（分别）视为理解相同的基本伪随机现象及其与结构的相互作用的分析和综合方法。计算机科学主要是数学的被动消费者，依赖于对结构的数学分析来构建所需的对象。我们建议通过使用随机性的计算视图来分析数学结构，将这种单向使用转变为完全成熟的合作。这个工具的初步应用，许多PI，已经导致了重大突破，无论是在新的理解数学对象，并在使用这些对象作为基础的建设，在计算机科学。最近的突破，从这种交叉施肥的例子包括工作的扩展凯莱图，提取器和产品定理，算术（和其他）进展的素数，并使用高尔斯？复杂性的标准。许多人依赖于伪随机性的概念计算工具，即任何一类测试都无法区分随机对象和正在讨论的对象之间的差异。这个概念出现在密码学的复杂性理论方法中，但此后在计算机科学中有广泛的应用性（例如去随机化概率算法）。