Computer Science
Tel-Aviv University

Coding Theory

Fall 2006


Lecture notes

Homework assignments

Some Information


Thursday 16:00-19:00, Orenstein 111

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

We won't follow any particular textbook. Still, here are some books I find useful:
Introduction to Coding Theory, by Ron Roth
Fundamentals of Error-Correcting 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, Reed-Solomon codes, Reed-Muller codes, Random codes, Justesen codes, Algebraic geometric codes, Johnson bounds, MacWilliams identities, Linear Programming bound, efficient decoding and encoding, list decoding, capacity-achieving list-decodable codes, NP-hardness of coding questions, applications to extractors and derandomization.
Attendance, homework assignments (once every week or two), and a final project
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, Reed-Solomon codes, multivariate polynomials over finite fields, Reed-Muller codes
Nov 23 Hadamard codes; Gilbert-Varshamov bound; Forney's construction and code concatenation; Zyablov bound (RS+GV); Justesen codes
Nov 30 Upper bound on codes: Plotkin bound, Elias-Bassalygo 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: Goldreich-Levin hard-core predicates
Jan 4 Local decoding of Reed-Muller codes; application to hardness on average of the permanent
Jan 11 Local list-decoding of Reed-Muller 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

Ideas for Projects