67902  Advanced Topics in Theoretical CS:
Pseudorandom Objects, Error Correcting Codes, and PCPs
Teacher: Irit Dinur
Location: Sprinzak 201
Time: Wednesdays 15:00  17:45
PROJECT PRESENTATION (+pizza party): Tuesday, February 20, 10am, Ross 63.
This course is intended for graduate students and advanced undergrads in
theoretical computer science or mathematics.
Requirements: Very basic knowledge in probability, algebra, and complexity.
Participants are expected to submit excercises, scribe notes for one lecture
and/or give one presentation. No exam, of course.

The presentation will be a chance to go more in depth on a specific subject.
Students can choose something from what we talked about during the course, read
a paper on it (which I will point you to), and give a presentation.

For the scribers, here is a sample
latex file, and the definition
file to go with it (both taken from Madhu Sudan's webpage). Check out
some neat latex links.
Unedited scribe notes:

Draft of Lecture 1 (1Nov2006, Robby Lampert) :
Introduction, error correcting codes, Hamming code and random codes.

Draft of Lecture 2 (8Nov2006, Noa Eidelstein) :
Decoding of random codes. Hadamard code. Reed Solomon code.

Draft of Lecture 3 (16Nov2006, Beny) :
Decoding of Reed Solomon Code. ReedMuller Code.

Draft of Lecture 4 (22Nov2006, Omer Lev) : Expanders. Expander Codes.

Draft of Lecture 5 (29Nov2006, Yoad Lustig) : Properties of expanders. Application for hardness amplification.

Draft of Lecture 6 (6Dec2006, Elad Eban) : Expander amplification lemma. Zigzag product.

Draft of Lecture 7 (13Dec2006, Rani Lekach) : End Zigzag Product. PCP Intro.
 Draft of Lecture 8 (20Dec2006, Ram Boukobza) :
Hardness of approximation and equivalence of PCP theorem and hardness of gapCSP.
 Draft of Lecture 9 (27Dec2006 Yonatan Amit) :
Gap Amplification. Snow...
 Draft of Lecture 10 (3Jan2007 Ezra Hoch and Yonatan Amit) :
Proof of gap amplification: preprocessing, and start of graph powering.
 Draft of Lecture 11 (10Jan2007 Naama Seri) :
Proof of gap amplification: graph powering.
 Draft of Lecture 12 (17Jan2007 Limor BenEphraim) :
Proof of gap amplification: end graph powering.
 Draft of Lecture 13 (25Jan2007 Lior Aronshtam) :
Alphabet Reduction, linearity testing.
 Draft of Lecture 14 (31Jan2007 Dvir Falik) :
Finish Alphabet Reduction.
Problem sets:
Some resources:
 Error Correcting Codes:
 Expander Graphs:
 PCPs: