0368.4159 A first course in derandomization

CS dept, Tel-Aviv University, Spring 2018

 

We meet at Schreiber 06.


 

Syllabus (including links and references)

 

Homework exercises

HW4 is due 7.1.19

 

A link to taking scribe notes

 

A link to the grading sheet

 

A link to the take home exam

 

 


 

 

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 ShaltielTopics in Pseudorandomness (Fall 2005-2006)

 

     David ZuckermanPseudorandomness and Combinatorial Constructions

 

     Michael. Luby and Avi WigdersonPairwise Independence and Derandomization

 

     Shlomo Hoory and Nathan Linial and Avi WigdersonExpander 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.

 

Scribe (Dori Medini)

 

2015-PM

 

 

2

Oct 22

The class NC. Some complexity background. Non-uniformity. Polynomial Identity testing. Markov, Chebyshev, K-wise ind.

Scribe (Eyal Golombek)

 

2015-k-wise

 

 

3

Oct 29

Chernoff.

A RNC algorithm for Maximal IS.

Scribe (Roy Nadler)

 

 

2015-Maximal-IS

M. LubyA 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.

Scribe (Or Karni)

 

 

5

Nov 12

Noam Parzenchevski

Error correcting codes.

RS.

Justensen code.

2017-ECC-Basics

 

2017-ECC-Concatenation

 

2017-ECC-Justensen

 

6

Nov 19

The Primality testing algorithm. Finite fields. Cyclotomic polynomials and their factorization over Fp.

Scribe (Or Karni + Ori Sberlo)

The original paper

7

Nov 26

The correctness proof of the AKS algorithm.

Scribe (Or Karni + Ori Sberlo)

 

8

Dec 3

Expanders.

Random walks on graphs.

Spectral analysis.

Deterministic amplification.

Scribe

 

 

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.

Scribe

 

11,12

Dec 24, 31

Space bounded computation. The Forbes, Kelley PRG: Iterative bounded independence+noise

Scribe

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).

2018-NW

 

2018-BPP-KarpLiptonThms

 

2018-IK

V. Kabanets, R. ImpagliazzoDerandomizing polynomial identity tests means proving circuit lower bounds