Randomness in Computing

提出的研究一方面涉及计算理论中出现的概率概念，另一方面涉及它对理解随机性本质的影响。具有难以处理的随机实例的问题理论比类似的最坏情况理论更微妙。必须使用构造展开式、编码理论和其他组合和代数技术。难平均问题的一个重要用途是生成伪随机字符串。相反，最坏情况下的负结果很少有应用，而最坏情况下的正结果对于许多简单的平均问题来说是无望的。

The research proposed is concerned with probabilistic concepts arising in the theory of computation on the one hand, and its effect on the understanding of the nature of randomness on the other. The theory of problems with intractable random instances is more subtle than similar worst-case theories. Constructive expanders, coding theory, and other combinatorial and algebraic techniques must be used. An important use of hard-on-average problems is the generation of pseudo-random strings. In contrast, worst-case negative results rarely have applications, while worst-case positive results are hopeless for many easy-on average problems.