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.