Error-Correcting Codes

(Combinatorial Methods in Complexity Theory)

Spring 2016



Course Info

Instructor: Swastik Kopparty (

Class Time and Place: Thursdays, 12 noon – 3pm, in Hill 009

Office Hours: Wednesday 10:00-11:00 (Hill 432)

Prerequisites: basics of algorithms, complexity theory, probability, graph theory, linear algebra, mathematical maturity.

References: various online sources, scribe notes.





This course will be an introduction to the theoretical aspects of error-correcting codes, with many applications to complexity theory.


Students will take turns scribing the lectures, and the notes will be put up here. There will be 2-3 problem sets.

Latex files for scribes: definitions, main file, guidelines.




·       Homework 1 (due Feb 4, but some parts are due earlier if you need permission to register)

·       Homework 2 (due March 24)


Lecture Schedule

·       January 21: the main problems of coding theory, basic bounds on codes (notes)

·       January 28: more bounds on codes, Shannon’s theorem for random errors (notes)

·       February 4: codes based on polynomials (notes)

·       February 11: concatenated codes (notes)

·       February 18: BCH codes (notes)

·       February 25: class cancelled (makeup class to be scheduled)

·       March 3: expander codes, expander distance amplification (notes)

·       March 10: class cancelled (makeup class to be scheduled)

·       March 17: SPRING BREAK

·       March 24: expander distance amplification, list-decoding (notes)

·       March 31: list-decoding, list-decoding Reed-Solomon codes (notes)

·       April 7: list-decoding concatenated codes, list-decoding Folded Reed-Solomon codes (notes)

·       April 14: list-decoding Folded Reed-Solomon codes, locally decodable codes based on polynomials (notes)

·       Tuesday April 19, 12 noon – 3pm: (NOTE UNUSUAL DAY) matching-vector codes (notes)

·       April 21: multiplicity codes (notes)

·       Tuesday April 26, 12 noon – 3pm: (NOTE UNUSUAL DAY) worst-case to average-case reductions, Fourier-based bounds for codes (notes)

·       April 28: codes better than random (notes)