About this course

\( \def\DTIME{\mathsf{TIME}} \def\NTIME{\mathsf{NTIME}} \def\DSPACE{\mathsf{DSPACE}} \def\NSPACE{\mathsf{NSPACE}} \def\P{\mathsf{P}} \def\NP{\mathsf{NP}} \def\L{\mathsf{L}} \def\NL{\mathsf{NL}} \def\PSPACE{\mathsf{PSPACE}} \def\NPSPACE{\mathsf{NPSPACE}} \def\EXP{\mathsf{EXP}} \def\NEXP{\mathsf{NEXP}} \def\RP{\mathsf{RP}} \def\coRP{\mathsf{coRP}} \def\ZPP{\mathsf{ZPP}} \def\PP{\mathsf{PP}} \def\FP{\mathsf{FP}} \def\sharpP{\#\mathsf{P}} \def\BPP{\mathsf{BPP}} \def\AC{\mathsf{AC}} \def\NC{\mathsf{NC}} \def\SC{\mathsf{SC}} \)

The main aim of this course is to expose students to basics of error correcting codes and its fascinating applications in various problems arising in Theoretical Computer Science (that may have nothing to do with codes !).

The course assumes a basic understanding of linear algebra, probability and familiarity with algorithms - arguing correctness and bounding runtime. A few handouts containing the necessary statements from these topics (with some pointers for further reading) will be provided.

Upon successfully completing the course, the student is expected to do the following.

Learning outcomes

1. Define basic notions in coding theory - rate, distance, errors, erasures, channel (BSC and BEC), defining linear codes (and duals) via generator and parity check matrices. Understand structured transformations on code and their effects on rate and distance.

2. Applying basic algebraic structures - groups, polynomial rings, ideals, vectorspace and finite field in solving problems arising in communication.

3. Recall as well as apply trade-offs involved in designing error correcting codes (Hamming, Singleton, Plotkin, Gilbert-Varshamov, Elias Bassalygo, Griesmer, Johnson bound).

4. Constructing codes that must meet certain rate-distance requirements, particularly - Reed Solomon codes, Reed Muller codes, BCH codes and expander based code constructions.

5. Explain and sketch efficient algorithms for decoding Reed Solomon codes, Reed Muller codes and BCH codes in (a) unique decoding, (b) list decoding, (c) local list decoding and (d) local recoverable settings along with rigorous arguments for correctness and runtime.

6. Apply error correcting codes in settings outside of communication - (a) Cryptography (Goldreich-Levin), (b) Combinatorics (Sunflowers, Shannon capacity), (c) Complexity theory (Worst-case to average-case reductions), (d) Quantum computing (Quantum error correction) and a few settings
   in Theoretical CS (constructing good hash functions, group testing)

Links to similar courses offered

• Algebraic Error Correcting codes by Mary Wooters
• Coding Theory by Prahlad Harsha
• Error Correcting Codes by Swastik Kopparty
• Topics in Error Correcting Codes by Mrinal Kumar
• Essential Coding Theory by Madhu Sudan