Randomness has been proven to be crucial for developing provably efficient algorithms and protocols, and the study of randomized algorithms has become a major topic in recent years. We investigate the role of randomness in computation through three aspects: First, we develop randomized algorithms for basic problems in computer science, or problems with practical constraints. Secondly, we analyze basic randomized protocols that have been used widely in practice and we aim to provide theoretical foundations for their performance. Thirdly, we study the role of randomness in these algorithms or protocols, e.g. via pseudo-randomness techniques.
Our group was founded in May 2013 in the Cluster of Excellence. It currently consists of He Sun, and Pavel Kolev.