Random Structures and Algorithms (Former Research Group)

Vision and Research Strategy

 

Randomness is a crucial component in the design and analysis of many efficient algorithms. 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 has also turned out to be a very useful tool in the analysis of deterministic algorithms. The resulting expected runtimes of the algorithms for real input distributions are often more relevant for practitioners than general worst-case bounds.

 

The group works on the efficient use of randomness in computer science.  One particular topic in this context are quasirandom methods. These are deterministic processes that imitate a particular property of a random process. They are designed to give the same limiting behavior (of some quantities of interest) as a random process, but often with faster convergence. In the last few years it has been shown that quasirandom algorithms can outperform deterministic and randomized algorithms in quality and runtime.

Composition of Group

The Random Structures and Algorithms Group headed by Tobias Friedrich was established in May 2011. The group consisted of one PhD student (Karl Bringmann) and one postdoc (Timo Kötzing).

Prof. Dr. Tobias Friedrich

Prof. Dr. Tobias Friedrich

Since August 2012, Tobias Friedrich is a professor at the Institute for Computer Science, Friedrich-Schiller-Universität Jena.

Publications