Coding Theory has been playing an important role in many areas of Engineering, Applied Math and Computer Science in topics such as communications, CS theory, networking, and security. This course will be a modern take on coding theory emphasizing probabilistic methods, power of randomization, and open research questions in discrete probability and extremal combinatorics. The topics covered will include (but will not be limited to) basic coding and information theory, soft-packing and Shannon capacity, threshold phenomenon in random graphs, polarization, algebraic codes, Reed-Solomon and Reed-Muller codes, list decoding, sparse-graphs and expander codes, algebraic combinatorics and codes, applications of codes.
This course is for graduate students and advanced undergraduate students (with permissions).
No Textbooks
Prerequisite: Linear algebra, probability
Instructor:
Arya Mazumdar arya@ucsd.edu https://mazumdar.ucsd.edu
Logistics:
Tue/Thu 12:30-13:50 WLH 2114
TA:
Nadim Ghaddar nghaddar@ucsd.edu
Office hours: Thu 14:00-15:00 in Atkinson Hall, next to room 4107
Lecture 1: Shannon and Hamming
Lecture 2: Hamming code and Sphere Packing
Lecture 3: Bounds on Codes
Lecture 4: Bounds on Codes - Random Channel
Lecture 5: Random Codes
Lecture 6: Codes on Graphs
Lecture 7: Expander Codes
Lecture 8: Spectral Expanders
Lecture 9: Belief Propagation
Lectures 10-11: Polar Codes
Lecture 12: Polar Codes (Cont'd)
Lecture 13: Reed-Muller Codes
Lecture 14: First-order Reed-Muller Codes and Covering Codes
Lecture 15: List Decoding
Lecture 16: Reed-Solomon Codes
Lecture 17: Decoding of Reed-Solomon Codes
Lecture 18: Concatenated Codes