Randomness and complexity

本研究计划研究随机算法在不同计算环境下的优势和局限性。随机算法是一种可以访问随机比特源并将其作为辅助输入来指导其行为的算法。在过去的二十年里，理解随机性在计算中的作用一直是一个引人入胜的研究领域，导致了几个基本的结果。现在众所周知，随机算法能够在特定环境下比已知的确定性算法更有效地执行一些计算任务，即使是那些不可能确定性的任务。也有很好的证据表明，随机化在一般情况下不会带来额外的力量。然而，我们对随机性作为一种资源的真正力量的理解还远远不够。本提案的目标是进一步探索各种计算模型中的随机性的力量，并找到这些结果在计算机科学其他领域的新应用。

This research program studies the strengths and limitations of randomized algorithms in various computational settings. A randomized algorithm is an algorithm that has access to a source of random bits and uses it as an auxiliary input to guide its behaviour. During the last two decades, understanding the role of randomness in computation has been an fascinating area of research leading to several fundamental results.It is now well known that randomized algorithms are capable of performing some computational tasks much more efficiently than known deterministic algorithms in specific settings, even those that are impossible deterministically. There is also good evidence that randomization does not give additional power in a general setting.However, our understanding of the true power of randomness as a resource is still far from complete. The goal of this proposal is to further explore the power of randomness in various computational models and to find new applications of these results to other areas of computer science.