Coding Theory CS294 - Fall 2017

EECS Courses:
Course Instructors: Tom Gur, Igor Shinkar
Time: Tuesdays 2:00-4:00PM
Location: 320 Soda Hall
Office Hours: Schedule an appointment via email (Tom or Igor)
Discussion forum:

Course Description: 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.

Tentative Syllabus:
  • Introduction, linear codes
  • Existential results, Gilbert-Varshamov bound
  • Limitations: Singleton bound, Plotkin bound, Elias-Bassalygo bound, Johnson bound
  • MRRW bound
Classical constructions of codes
  • 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
Local decodability and testability
  • 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

Prerequisites: 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.

Related courses:
- Venkatesan Guruswami's course notes.
- Madhu Sudan's course notes.
- Luca Trevisan's course notes.

Requirements: Completing the course requires
  • regular attendance and participation,
  • scribing,
  • 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
MRRW bound

Lecture 7 - October 10 - Igor MRRW bound - cont.

Lecture 8 - October 17 - Tom Expander codes

Lecture 9 - October 24 - Igor Locally decodable codes, Locally testable codes

Lecture 10 - November 7 - Tom Multiplicity codes

Lecture 11 - November 14 - Peter Tensor Codes

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