Randomness, Non-determinism, and Symmetry Breaking

随机性、非确定性和对称性破缺

• 批准号: 0830719
• 负责人: Leonid Levin
• 金额: --
• 依托单位: Trustees of Boston University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2011-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830719&HistoricalAwards=false
• 关键词: Randomness; Non; determinism; Symmetry; Breaking

Explosive development of computer technology outpaces theoretical understanding and leaves many of its pillars on shaky ground. As an extreme example, if it turns out that P=NP or that one-way functions do not exist, all of public-key cryptography and many tools crucial for national and personal security would be permanently incapacitated. In this (unlikely but possible) event, much of the computer infrastructure would have to be redesigned on a less impressive scale. On the other hand, many great advances cannot be foreseen even now due to insufficient theoretical understanding of basic issues.Computations rarely run in deterministic isolation. They interact with users and adversaries, with random events called by algorithms or generated by the context, with delays and glitches from the system, hardware, and distributed infrastructure, etc. Some of these interactions are hard to model, but even those with straightforward mathematical models are often very hard to analyze. Randomness and non-determinism are two basic "freedoms" branching out of the concept of deterministic computation which play a crucial role in computing theory. Yet our understanding of their role and power is minimal. Even a gradual progress in understanding these phenomena and their relationship to each other and to other concepts would be important.An example of achievements in this direction is the discovery of generic relationship between one-way functions and deterministic generation of randomness. Another is the concept of transparent (also called holographic, or PCP) proofs and computations. A number of interesting techniques useful for quite different results in these areas have been accumulated: low-degree polynomials and Fourier transforms over low-periodic groups, related to classical results on error-correcting codes and hashing, expander graphs, hierarchic structures, etc. The PI will continue his investigation of such concepts and of the power of these and other related techniques.Symmetry is one of the central phenomena in many fields. In computation it can simplify analysis, provide uniformity and redundancy useful, e.g., for error-correction. On the other hand, it can cause indecisiveness, deadlocks and complicate initialization and organization of computing processes. Breaking symmetries is as essential a task as maintaining them. A study of a number of mathematical and algorithmic tools useful for symmetry breaking is intended. Examples include Thue sequences, aperiodic tilings, extensions of the concept of flat connections from manifolds to graphs, and others.The work will advance discovery and understanding via dissemination of the results through talks, papers, and Web pages, PI's own and those of others. This research has implications in many close and remote areas. Indeed, the concepts the PI is interested in such as, e.g., randomness, are fundamental in a broad variety of fields of knowledge.

计算机技术的爆炸性发展超过了理论理解，使其许多支柱摇摇欲坠。作为一个极端的例子，如果P = NP或单向函数不存在，那么所有的公钥密码学和许多对国家和个人安全至关重要的工具都将永久失效。 在这种情况下（不太可能，但有可能），许多计算机基础设施将不得不重新设计，规模不那么令人印象深刻。 另一方面，由于对基本问题的理论认识不足，许多重大进展至今仍无法预见，计算很少在确定性孤立状态下运行。它们与用户和对手交互，与算法调用或上下文生成的随机事件交互，与系统、硬件和分布式基础设施等的延迟和故障交互。随机性和非确定性是确定性计算概念的两个基本分支，在计算理论中起着至关重要的作用。 然而，我们对他们的作用和力量的了解却微乎其微。 在理解这些现象及其相互关系和与其他概念的关系方面，即使是逐步取得进展也是很重要的，这方面的成就的一个例子是发现单向函数和随机性的确定性生成之间的一般关系。另一个是透明（也称为全息或PCP）证明和计算的概念。 在这些领域积累了许多有益于取得不同结果的有趣技术：低次多项式和傅立叶变换在低周期群，有关的经典结果纠错码和散列，扩展图，层次结构，PI将继续研究这些概念以及这些和其他相关技术的力量。对称性是许多技术中的核心现象之一。领域的 在计算中，它可以简化分析，提供有用的一致性和冗余性，例如，用于纠错。另一方面，它会导致计算过程的不确定性、死锁以及复杂的初始化和组织。打破对称性和维持对称性一样重要。研究的一些数学和算法工具的对称性破缺是有用的。 例子包括图厄序列，非周期平铺，平面连接的概念从流形到图的扩展，以及其他。这项工作将通过讲座，论文和网页，PI自己和其他人的结果传播，促进发现和理解。这项研究在许多近距离和偏远地区都有意义。 事实上，PI感兴趣的概念，例如，随机性，是各种知识领域的基础。