Hasso-Plattner-InstitutSDG am HPI
Hasso-Plattner-InstitutDSG am HPI

HPI Kolloquium: "Do we need randomness?"

Prof. Dr. Tobias Friedrich (Hasso-Plattner-Institut an der Universität Potsdam)

28. Mai 2015


Computers are typically described as deterministic machines that cannot make any random decisions. However, randomness is relevant for computer science in various forms. First, it can be used to make random decisions in an algorithm. Such randomized algorithms are often much simpler to implement and achieve good performance in the average case. Second, randomness can be a very useful tool in the analysis of (deterministic) algorithms. The resulting expected runtimes for real input distributions can be more meaningful for practical applications than general worst-case bounds.

This talk will present the use of randomness in a number of different domains. Starting from the very basics, it will discuss randomness in philosophy, quantum mechanics, mathematics, programming, social networks and optimization. No prior knowledge about randomness or any higher mathematics is needed to enjoy the talk.


Tobias Friedrich just established his chair at the Hasso Plattner Institute. His algorithm engineering research group just started in April 2015. Before he came to Potsdam, he was heading the chair for theoretical computer science at University of Jena, Germany and senior researcher at the Max Planck Institute for Computer Science. He has received his M.Sc degree in computer science from University of Sheffield, United Kingdom, his M.Sc. degree in mathematics from University of Jena, Germany, and his Ph.D. in computer science from Saarland University, Germany. His research considers the foundations of computer science in the areas algorithms and complexity. Special focuses of his work are random structures and methods.