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.