Computer Science
|
|
Fall 2006 |
| Lectures |
Thursday 16:00-19: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 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. |
| 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, 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 |
