IPEC course Randomness
Responsible
Prof. Dr. Joachim von zur Gathen
Lecture
Time & Place
26 March 2007, 9:15h, b-it Marschallsaal
Contents
The use of randomness in computation is the topic of this course:
- Some examples: finger-printing huge databases, congestion-avoiding routing in networks, testing integers for primality.
- Sources of true randomness.
- Distilling excellent randomness out of a miserable source of randomness
- Extending a small amount of true randomness to a huge amount of pseudorandomness; the latter is just as good for computational purposes.
one week block,
26 March 2007 - 31 March 2007, 9:00h-18:00h,
b-it Marschallsaal
Material
- Rajeev Motwani, Prabhakar Raghavan: ''Randomized Algorithms'', 1995
- Ivars Petersen, ''The Jungles of Randomness'', 1998
- Rod Downey, David Hirschfeld, ''Algorithmic randomness and complexity'', 2006
Allocation
equivalent to 2+2 SWS