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.

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

• Problem set #1 due Nov 22
• Problem set #2 due Dec 20 Dec 27

• Error Correcting Codes:
  • A course on Essential Coding Theory given by Madhu Sudan at MIT.
  • Expander codes, by M. Sipser and D. Spielman. Also the survey by Venkatesan Guruswami.
  • A course on Codes and Pseudorandom Objects given by Venkatesan Guruswami at the University of Washington.
• Expander Graphs:
  • A course on Expander graphs and their applications given by Nati Linial and Avi Wigderson at the Hebrew U.
  • Entropy waves, the Zig-Zag graph product, and new constant-degree expanders and extractors, by O. Reingold, S. P. Vadhan and A. Wigderson.
• PCPs:
  • A course on the PCP Theorem and hardness of approximation, given by Venkatesan Guruswami and Ryan O'Donnell.
  • The PCP Theorem by Gap Amplification, by Irit Dinur.
  • A paper by Jaikumar Radhakrishnan and Madhu Sudan.