0368.4159 A first course in derandomization
CS dept, Tel-Aviv University,
Spring 2018
|
Syllabus (including links and references)
|
Lecture Monday, 14:00-17:00,
Schreiber 06 Instructor Amnon Ta-Shma | Schreiber 127
| 5364 Open
for Undergrad
and grad students. Grading
policy 50%
take-home exam, the
rest is exercises and participation in class. |
|
|
Textbooks
and links |
·
Avi Wigderson – Math and
Computation ·
Salil Vadhan – Pseudorandomness ·
Ronen Shaltiel, Topics
in Pseudorandomness (Fall 2005-2006) ·
David Zuckerman, Pseudorandomness and
Combinatorial Constructions ·
Michael. Luby and Avi Wigderson, Pairwise
Independence and Derandomization ·
Shlomo Hoory and Nathan Linial and Avi Wigderson, Expander
Graphs and their applications
|
|
|
|
|
|
Date |
Class Topic |
Lecture notes |
References |
|
1 |
Oct 15 |
A RNC algorithm for Perfect matching. The
isolation lemma. Finding a perfect matching in parallel. |
|
|
|
2 |
Oct 22 |
The class NC. Some complexity background.
Non-uniformity. Polynomial Identity testing. Markov, Chebyshev, K-wise ind. |
|
|
|
3 |
Oct 29 |
Chernoff. A
RNC algorithm for Maximal IS. |
|
M. Luby, A simple parallel algorithm for the maximal independent set problem |
|
4 |
Nov 5 |
Finishing
the proof of the RNC algorithm. Derandomizing it to
get an NC algorithm. |
|
|
|
5 |
Nov 12 Noam Parzenchevski |
Error correcting codes. RS.
Justensen code. |
|
|
|
6 |
Nov 19 |
The
Primality testing algorithm. Finite fields. Cyclotomic
polynomials and their factorization over Fp. |
||
|
7 |
Nov 26 |
The
correctness proof of the AKS algorithm. |
|
|
|
8 |
Dec 3 |
Expanders.
Random
walks on graphs. Spectral
analysis. Deterministic
amplification. |
|
|
|
9 |
Dec 10 |
Parity
samplers. Distance amplification by expanders. |
|
|
|
10 |
Dec 17 |
Fourier
transform for Z_2^n. Eps-biased spaces. BLR test. (k,eps) biased distribution. Vazirani
XOR lemma. |
|
|
|
11,12 |
Dec 24, 31 |
Space
bounded computation. The Forbes, Kelley PRG: Iterative bounded independence+noise |
M. Forbes,
Z. Kelley, Pseudorandom Generators
for Read-Once Brasnching Programs, in any order. |
|
|
13 |
Jan 7 |
A
little bit about he BPP vs. P problem: NW:
Hardness implies PRG. KI:
Derandomization implies hardness (sort of). |
|
V. Kabanets,
R. Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds. |