AF:EAGER: Randomness, Non-determinism, and Symmetry Breaking

计算很少在确定性隔离中运行。 它们与用户和对手交互，与算法调用或上下文生成的随机事件交互，与系统、硬件和分布式基础设施等的延迟和故障交互。但即使是那些有简单数学模型的，也往往很难分析。随机性和非决定性是两种基本的“自由”。确定性计算的概念的分支，在计算理论中起着至关重要的作用。然而，我们对他们的作用和力量的了解却微乎其微。 在理解这些现象及其相互关系和与其他概念的关系方面，即使是逐步取得进展也是很重要的，这方面的成就的一个例子是发现单向函数和随机性的确定性生成之间的一般关系。另一个是透明的概念（也称为全息，或PCP）证明和计算。在这些领域中，已经积累了许多有趣的技术，可用于完全不同的结果：低次多项式和傅立叶变换在低周期群，有关的经典结果纠错码和散列，扩展图，层次结构，这项研究是继续PI对这些概念以及这些和其他相关技术的力量的调查。对称性是许多领域的中心现象之一。 在计算中，它可以简化分析，提供有用的一致性和冗余，例如，用于纠错。另一方面，它会导致计算过程的不确定性、死锁以及复杂的初始化和组织。打破对称性和维持对称性一样重要。计划研究一些对对称破缺有用的数学和算法工具。例子包括图厄序列，非周期平铺，从流形到图的平坦连接的概念的扩展，以及其他。对我们理解随机性、非决定性、复杂性和对称性破缺做出了重大贡献。 这个项目将促进我们对这些领域的了解。

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 research is to continue PI's 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 computations 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 planned. Examples include Thue sequences, aperiodic tilings, extensions of the concept of flat connections from manifolds to graphs, and others.In prior work, the P.I. has made major contributions to our understanding of randomness, nondeterminism, complexity, and symmetry breaking. This project will advance our understanding of those areas.