Instructor: Swastik
Kopparty (swastik.kopparty@gmail.com)
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.
Syllabus
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
·
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)