Content (Tentative)

Introduction to error correcting codes

• Definitions and introduction to error correcting codes, Hamming and Shannon models
• Linear codes and existence of good linear codes
• Various bounds on the existence of codes

Polynomial based codes

• Reed Solomon codes, Reed Muller Codes
• Berlekemp-Welch algorithm for unique decoding decoding
• Unique decoding of RM codes on algebraically nice sets
• List decoding and list decoding algorithms for RS/RM codes

Local Decoding

• Locally decodable codes
• Hadamard Code, Multiplicity codes, Matching Vector codes

Operations on codes

• Alphabet Reduction
• Distance Amplification

Some other topics

• Polar codes
• Codes for stochastic noise
• Applications of codes in complexity theory - worst case hardness to average case hardness, private information retrieval