Randomness and Non-Determinism

随机性和非确定性是扩展确定性计算概念的两个基本“自由”。虽然这些扩展的力量仍然是计算理论中的一个深层次的谜团，但它们之间的关系正在出现一些模糊的模式。更有趣的是，类似技术的模式在这一领域产生了截然不同的结果。多线性和低次多元多项式以及低周期群上的傅里叶变换等思想似乎很有启发性。相关的是关于纠错码或散列的经典结果。其他一些技术，如扩展图，基于不同的数学，但可以用于相同的目的。这项研究旨在进一步理解随机性和非决定论的力量，并特别关注数学技术的作用。它使用了如上所述的数学技术。

Randomness and non-determinism are two basic "freedoms" stretching the concept of deterministic computation. While the power of these extensions remains a deep mystery of computing theory, some vague pattern is emerging in relationships between them. The pattern of similar techniques instrumental for quite different results in this area is even more interesting. Ideas like multilinear and low-degree multivariate polynomials and Fourier transformation over low-periodic groups seem very illuminating. Related are classical results on error- correcting codes or hashing. Some other techniques such as expander graphs are based on different mathematics but can be used for the same ends. The research is directed towards further understanding of the power of randomness and non- determinism with special attention to the role of mathematical techniques. It employs mathematical techniques such as the ones mentioned above.