חיפוש חדש  חזור
מידע אישי לתלמיד

שנה"ל תשע"ט

  קורס ראשון בדרנדומיזציה
  Derandomization 1                                                                                    
0368-4159
מדעים מדויקים
קבוצה 01
סמ'  א'1400-1700006שרייבר - מתמטיקהשיעור פרופ תא שמע אמנון
ש"ס:  3.0

סילבוס מקוצר

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.

להצהרת הנגישות


אוניברסיטת ת