Computer Science


Fall 2006 
Lectures 
Thursday 16:0019:00, Orenstein 111 
Instructor 
Oded Regev  Schreiber 121  6406354 
Lecture notes on the web 
Madhu Sudan's courses: 2004,
2002,
2001, and
2000.
Most complete lecture notes are in 2001. Luca Trevisan's course 
Textbooks 
We won't follow any particular textbook. Still, here are some books I find useful: Introduction to Coding Theory, by Ron Roth Fundamentals of ErrorCorrecting Codes, by W. Cary Huffman, Vera Pless Coding Theory: A First Course, by San Ling, Chaoping Xing Introduction to Algebra, by Peter J. Cameron Introduction to Finite Fields and their Applications, by Rudolf Lidl, Harald Niederreiter; or the complete version Elements of Information Theory, by Thomas M. Cover, Joy A. Thomas 
Preliminary syllabus 
Codes, Linear Codes, Singleton bound, ReedSolomon codes, ReedMuller codes, Random codes, Justesen codes, Algebraic geometric codes, Johnson bounds, MacWilliams identities, Linear Programming bound, efficient decoding and encoding, list decoding, capacityachieving listdecodable codes, NPhardness of coding questions, applications to extractors and derandomization. 
Requirements 
Attendance, homework assignments (once every week or two), and a final project 
Prerequisites 
Mathematical maturity is a must for this class. In addition, familiarity with the basics of probability, probabilistic method, algebra (especially finite fields), analysis of algorithms, and computational complexity would be helpful. 
Useful links 
Luca Trevisan's survey
on applications of coding theory in computational complexity Venkat Guruswami's thesis on applications of coding theory in computational complexity (newer version available here) Madhu Sudan's lecture notes on algebra and computation David Wilkins's lecture notes on algebra 
Date  Class Topic 
Oct 26  Information theory (see here for Shannon's paper); source coding; entropy, conditional entropy, mutual information, conditional mutual information, data processing inequality 
Nov 2  Random access codes (lower bound, a quantum example); noisy coding theorem and its converse for BSC 
Nov 9  Hamming codes, linear codes (generator matrix, parity check matrix, systematic codes, computational issues), Hamming bound, pefect codes, mention BCH codes 
Nov 16  Singleton bound, univariate polynomials over finite fields, ReedSolomon codes, multivariate polynomials over finite fields, ReedMuller codes 
Nov 23  Hadamard codes; GilbertVarshamov bound; Forney's construction and code concatenation; Zyablov bound (RS+GV); Justesen codes 
Nov 30  Upper bound on codes: Plotkin bound, EliasBassalygo bound (based on the Johnson bound), MacWilliams identities (using Fourier transform) 
Dec 7  The LP bound, its dual formulation, and an example of an application 
Dec 14  Algorithmic tasks, decoding RS 
Dec 21  Decoding RS from errors and erasures, decoding concatenated codes using the GMD decoder, polynomial time decodable codes achieving Shannon capacity, multivariate polynomials 
Dec 28  List decoding RS (see these relections and Madhu's overview); local (list)decoding of Hadamard codes (see Trevisan's survey), application: GoldreichLevin hardcore predicates 
Jan 4  Local decoding of ReedMuller codes; application to hardness on average of the permanent 
Jan 11  Local listdecoding of ReedMuller codes (STV); Yekhanin's approach to list decodeable codes 
Jan 18  Yekhanin's basic and main constructions 
Jan 25  Cyclic codes and their algebraic representation as ideals, and the rest of Yekhanin's construction 