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 (1-Nov-2006, Robby Lampert) :
Introduction, error correcting codes, Hamming code and random codes.
Draft of Lecture 2 (8-Nov-2006, Noa Eidelstein) :
Decoding of random codes. Hadamard code. Reed Solomon code.
Draft of Lecture 3 (16-Nov-2006, Beny) :
Decoding of Reed Solomon Code. Reed-Muller Code.
Draft of Lecture 4 (22-Nov-2006, Omer Lev) : Expanders. Expander Codes.
Draft of Lecture 5 (29-Nov-2006, Yoad Lustig) : Properties of expanders. Application for hardness amplification.
Draft of Lecture 6 (6-Dec-2006, Elad Eban) : Expander amplification lemma. Zigzag product.
Draft of Lecture 7 (13-Dec-2006, Rani Lekach) : End Zigzag Product. PCP Intro.
- Draft of Lecture 8 (20-Dec-2006, Ram Boukobza) :
Hardness of approximation and equivalence of PCP theorem and hardness of gap-CSP.
- Draft of Lecture 9 (27-Dec-2006 Yonatan Amit) :
Gap Amplification. Snow...
- Draft of Lecture 10 (3-Jan-2007 Ezra Hoch and Yonatan Amit) :
Proof of gap amplification: preprocessing, and start of graph powering.
- Draft of Lecture 11 (10-Jan-2007 Naama Seri) :
Proof of gap amplification: graph powering.
- Draft of Lecture 12 (17-Jan-2007 Limor Ben-Ephraim) :
Proof of gap amplification: end graph powering.
- Draft of Lecture 13 (25-Jan-2007 Lior Aronshtam) :
Alphabet Reduction, linearity testing.
- Draft of Lecture 14 (31-Jan-2007 Dvir Falik) :
Finish Alphabet Reduction.
- Error Correcting Codes:
- Expander Graphs: