| |||||||||||||||||||||||||||||||||
קורס ראשון בדרנדומיזציה
Derandomization 1 |
0368-4159 | ||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
מדעים מדויקים | |||||||||||||||||||||||||||||||||
|
A first course in Derandomization
Randomness is extremely useful for developing fast and simple algorithms. Derandomization often enables one to convert a randomized algorithm into a deterministic one. In this course we will develop tools and techniques for the design and analysis of efficient randomized algorithms and their derandomization. A tentative list of possible topics follows.
- A probabilistic algorithm for finding a maximal independent set in parallel, and its derandomization using pairwise independence.
- A probabilistic algorithm for finding a perfect matching in parallel. The identity testing problem.
- The Hardness vs. Randomness Paradigm
- The converse: Derandomization implies Hardness
We will use various tools, e.g. from: pairwise independence, eps-bias, k- wise and almost k-wise independence, expanders, extractors, error correcting codes and pseudo-random- generators.