Coding Theory CS294 - Fall 2017
: Tom Gur, Igor Shinkar
: Tuesdays 2:00-4:00PM
: 320 Soda Hall
: Schedule an appointment via email (Tom
: This course offers a graduate level introduction to error-correcting codes, with an emphasis on codes exhibiting a robust local-to-global structure that admit sublinear-time algorithms for tasks such as local testability and local decodability. Such locally testable codes (LTCs) and locally decodable codes (LDCs) play a key role in various fields of theoretical computer science, such as interactive proofs, PCPs, and property testing. The course is geared towards preparing the students for research in the area, and lectures will frequently present open problems and suggestions for future research.
Classical constructions of codes
- Introduction, linear codes
- Existential results, Gilbert-Varshamov bound
- Limitations: Singleton bound, Plotkin bound, Elias-Bassalygo bound, Johnson bound
- MRRW bound
Local decodability and testability
- Polynomial codes: Reed-Solomon, Reed-Muller, BCH codes
- Concatenated codes: Zyablov bound, Justesen code, Wozencraft ensemble
- Expander codes and linear time error-correction
- List decodable codes
- Algebraic geometry codes
- The Goldreich-Levin algorithm
- Definitions of locally testable/decodable codes
- BLR linearity testing
- Tensor codes, local testing of tensor codes
- Rate lower bounds for LDCs
- 3-query LDCs of subexponential length
- Matching vector codes
- High rate LTCs with small query complexity
- Connections between LTCs and Cayley graphs
- Multiplicity codes
- Codes obtained from lifling
: The official prerequisite is CS 170 (or equivalent). All students with "mathematical maturity" (algorithms, and discrete probability) and curiosity are welcome.
Standard books for reference
- Introduction to Coding Theory Jacobus H. van Lint. Springer-Verlag, Berlin, 1999.
- Introduction to Coding Theory Ron M. Roth, Cambridge University Press, 2006.
- Theory and Practice of Error-Control Codes Richard E. Blahut. Addison-Wesley, Reading, Massachusetts, 1983.
- The Theory of Error Correcting Codes F.J. MacWilliams and N.J.A. Sloane. North-Holland, Amsterdam, 1981.
- Algebraic Codes for Data Transmission Richard E. Blahut, Cambridge University Press, 2003.
- Venkatesan Guruswami's course notes
- Madhu Sudan's course notes
- Luca Trevisan's course notes
: Completing the course requires
- regular attendance and participation,
- final project.
Please use this TeX
file for scribes.
Lecture 1 - August 29 - Tom
Introduction, Basics definitions (rate, distance)
Linear codes, generating matrices and parity check matrices
Hamming code, Hadamard code
Lecture 2 - September 5 - Igor
Gilbert-Varshamov bound (random construction)
Elementary bounds: Hamming bound, Singleton bound, Plotkin bound
Lecture 3 - September 12 - Tom
Polynomial codes: Reed-Solomon, BCH codes, Reed-Muller
Lecture 4 - September 19 - Igor
Concatenated codes: Justesen codes, Wozencraft ensemble, Zyablov bound
Lecture 5 - September 26 - Tom
Introduction to Algebraic Geometry codes
Lecture 6 - October 3 - Igor
Elias-Bassalygo bound, Johnson bound
Lecture 7 - October 10 - Igor
MRRW bound - cont.
Lecture 8 - October 17 - Tom
Lecture 9 - October 24 - Igor
Locally decodable codes, Locally testable codes
Lecture 10 - November 7 - Tom
Lecture 11 - November 14 - Peter
Lecture 12 - November 21 - Tom
High rate locally decodable and locally testable codes
Lecture 13 - November 28 - Igor
3-Query locally decodable codes of subexponential length