Campus Event Calendar

Event Entry

What and Who

Use and Avoidance of Randomness

Tobias Friedrich
Max-Planck-Institut für Informatik - D1
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS  
MPI Audience

Date, Time and Location

Thursday, 13 December 2007
30 Minutes
E1 4


Randomness is a crucial component in the design and analysis of many efficient algorithms. The thesis covers three aspects of randomness in computer science. In the first chapter we examine a deterministic analogue to the random walk and prove that it resembles the random walk closely on a two-dimensional grid, but not on regular trees. We also propose and analyse a quasirandom analogue to the broadcasting model for disseminating information in networks and show that it achieves similar or better broadcasting times with a greatly reduced use of random bits.

In the second chapter we present the first average-case analysis of three different algorithms for maintaining a topological ordering of the nodes of a directed acyclic graph under dynamic updates. We prove an expected runtime which is significantly less than the best known worst-case bound for this problem.

We finish with a third chapter that deals with randomized search heuristics. We examine the impact of different diversity mechanisms on the runtime of a single-objective evolutionary algorithm. We also show how this can exponentially slow down evolutionary algorithms for multi-objective problems.


Tobias Friedrich
--email hidden
passcode not visible
logged in users only

Tobias Friedrich, 11/30/2007 16:00
Tobias Friedrich, 11/30/2007 15:58 -- Created document.