|Dec 21, 2001|
|EECS 598-02 Randomized Computation
|Winter 2002 |
Instructor: Satyanarayana V. Lokam (firstname.lastname@example.org)
Time and Place: Tue and Thu 11:30 AM -- 1:30 PM, 3433 EECS.
Credit Hours: 4 CSE students can take this course for 500+ level credit.
Prerequisites: A basic course in algorithms or computational complexity and familiarity with elementary algebra and probability theory.
Description: For several important problems, use of randomness yields the most efficient algorithms known, or the simplest, or both. In fact, randomness is essential for certain tasks in cryptography and distributed computation. As a result, research in randomized algorithms has seen a phenomenal growth in recent years. In the first half of this course, we will study a collection of techniques for effectively using randomization and for analyzing randomized algorithms. We will pick examples from a variety of settings and problem areas.
Given that randomization helps, where do computers get their randomness from? In practice, we often use Pseudo-Random Generators (PRG's). But, when is the output of a PRG ``random enough" to replace a source of pure random bits? How do we construct such good PRG's? Even assuming computers do have access to ``pure randomness," how dramatic a speedup can we achieve using randomness? In the second half of the course, we will study recent results that address such issues. Important results in this area have rigorously established the intimate relations among the notions of randomness, computation,and information.
Attempts to understand some basic scientific questions, use of simple, but elegant, mathematics, and building rigorous foundations for important practical applications are some of the interesting highlights of this course.
Grading: Homework and term papers/final projects.
- Background from Probability Theory
- Randomized Algorithms
- Pseudo-Random Generators
Term Paper/Final Project: 50%
For more up-to-date information, please visit: http://www.eecs.umich.edu/~satyalv/rand/