Topics in Error-Correcting Codes
CSC2429/MAT1304, Spring 2022
Course Info
Instructor: Swastik Kopparty (swastik.kopparty@utoronto.ca)
Class Time and Place: Thursdays 1pm-3pm, Bahen Center 2145
Please email me if you are not registered and want to be added to the mailing list.
Please use the course piazza site for questions.
Homework
Scribing
Latex file for scribing,
Latex definitions file.
Scribing guidelines.
Lectures
- September 8: the fundamental questions about codes, the Hamming bound, the Gilbert-Varshamov bound, Hamming codes
(notes)
- September 15: linear codes, random codes, the Plotkin bound
(notes)
- September 22: the Hadamard codes, the Singleton bound, Reed-Solomon codes, dual of the Reed-Solomon code
(notes)
- September 29: BCH codes, code concatenation, explicit asymptotically good codes
(notes)
- October 6: Decoding Reed-Solomon codes
(notes)
- October 13: Fourier analysis, R vs delta for delta near 1/2
(notes)
- October 20: Expander graphs, Sipser-Spielman expander codes
(notes)
- October 27: (Absolute) spectral expansion, Tanner expander codes
(notes)
- November 3: ABNNR and AEL expander codes
(notes)
- November 10: NO CLASS (Reading Week)
- November 17: Random walks on expanders, randomness efficient error-reduction
(notes)
- November 24: the zig-zag product
(notes)
- December 1: Ta-Shma's epsilon-balanced codes
Papers for reading projects
- Local decoders for multivariate polynomial codes https://madhu.seas.harvard.edu/papers/1992/gemmell.pdf
-
The Goldreich Levin theorem: https://cs.stanford.edu/people/trevisan/pacc/lecture08.pdf
- On 2 query linear locally decodable codes https://link.springer.com/article/10.1007/s00037-006-0216-3
- List decoding Reed-Solomon codes http://people.csail.mit.edu/madhu/papers/1996/reeds-journ.pdf
- Decoding multivariate polynomial codes https://www.math.toronto.edu/swastik/RM-productset-eccc-version.pdf
- Almost k-wise independence https://www.cs.tau.ac.il/~nogaa/PDFS/aghp4.pdf
- Concatenated codes meeting the GV bound https://ieeexplore.ieee.org/document/1056765
- Decoding expander codes https://ieeexplore.ieee.org/document/910593
- Beating the GV bound a tiny bit https://ieeexplore.ieee.org/document/910593
- Beating the GV bound a tiny bit with linear codes https://arxiv.org/abs/0708.4164
- The linear programming upper bound for codes (via Fourier analysis) https://arxiv.org/abs/math/0702425