Randomness in Computing

几十年的研究未能揭开两个基本“自由”的神秘面纱，这两个基本“自由”延伸了确定性计算的概念：随机性和非确定性。然而，近年来，他们之间的关系出现了一些模糊的模式。更值得注意的是，在这一领域中，对完全不同的结果有帮助的技术模式：多线性和低次多元多项式，低周期群上的傅立叶变换，与纠错码或散列的经典结果相关。一些基于不同数学的技术，如展开图，也非常相关。这个项目继续使用上述或类似的技术来调查随机性和非决定论的力量。研究的几个具体方向是：np问题的平均情况（而不是最坏情况）难解性的概念和具体例子以及单向函数逆问题；消除单向函数的简并性是有效生成伪随机比特的障碍。改进和简化了容错计算和通信。

CCR-9820934LevinDecades of research failed to demystify the power of the two basic "freedoms" stretching the concept of deterministic computation: randomness and non-determinism. In recent years, however, some vague pattern is emerging in relationships between them. Even more notable seems the pattern of techniques instrumental for quite different results in this area: multilinear and low-degree multivariate polynomials, Fourier transformation over low-periodic groups, related to classical results on error-correcting codes or hashing. Some techniques based on different math, like expander graphs, also emerge as very relevant. This project continues investigation of the power of randomness and non-determinism using the above or similar techniques. Several specific directions of the research are:The concept and specific examples of average-case (rather than worst case) intractability of NP-problems and problems of inverting one-way functions; removing degeneracy of one-way functions as an obstacle to efficient generation of pseudo-random bits. Improvement and simplification of fault-resistant computation and communication.