## A mini course on Coding Theory - An Algorithmic Viewpoint (August 2016)

Location: A201
Instructors :

#### Problem Sets

1. Problem Set 1 [pdf]
2. Problem Set 2 [pdf]

#### Lectures

 3 Aug 1. Fundamentals of coding: Shannon, Hamming and some basics Administrivia, Introduction to codes, Shannon and Hamming's model of channels, Hamming codes, Shannon noisy channel coding theorem, codes -- a formal treatment, Hamming bound. Ref: [Sud13 (Lec 1-2), Gur14 (Items 1 and 3)] 5 Aug 2. What we can and can't do Dual of a code, Hadamard code, Hamming bound, Gilbert Varshamov bound, Plotkin bound, Singleton bound. Ref: [Sud13 (Lec 3-4), Gur14 (Items 1, 2 and 4)] 8 Aug 3. Reed-Solomon code: the one code to rule them all (Part I) MDS codes, Algebraic codes: Reed-Solomon codes, BCH codes, Berlekamp-Welch unique decoding algorithm for RS codes. Ref: [Sud13 (Lec 6,7 and 10), Gur14 (Items 6-7)] 10 Aug 4. Reed-Solomon code: the one code to rule them all (Part II) List-decoding, Johnson bounds, list-decoding of RS codes (Sudan's algorithm). Ref: [Sud13 (Lec 12), [GRS15 (Chap. 7 and 13)] 19 Aug 5. Reed-Solomon code: the one code to rule them all (Part III) Guruswami-Sudan algorithm for list-decoding of RS codes, Reed-Muller codes. Ref: [Sud01 (Lecture 13, 4)] 22 Aug 6. Local-list decoding algorithm for the Hadamard code Goldreich-Levin algorithm. Ref: [Luc09 (Lectures 11-12)] 24 Aug 7. Expander codes - part I Codes based on graphs: Gallager, Tanner, Sipser-Spielman; expander codes and decoding algorithms. Ref: [notes, Sud13 (Lectures 14-15), Gur14 (Item 5)] 26 Aug 8. Expander codes - part I Expander codes and decoding algorithms, Tanner codes, Alon-Edmonds-Luby codes Ref: [notes, Gur14 (Item 5), Kop16 (Lecture 7)] 29 Aug 9. Locally decodable codes - Part I Locally decodable codes - definition, Hadamard codes, Reed-Muller codes, Matching-vector codes. Ref: [notes, Sud12 (Lectures 23-24), Gop09] 31 Aug 10. Locally decodable codes - Part II Matching-vector codes, Grolmusz's construction of matching vector families, OR representation Ref: [notes, Sud12 (Lectures 23-24), Gop09] 13 Sep 11. Polar codes - Part I (Guest Lecturer: Ramprasad Saptharishi) Review of Shannon's channel model; BSC, BEC and their capacities; Polarization, Arikan's Theorem Ref: [GC13 (parts of Lectures 1, 2, 8, 10 and 11)] 15 Sep 12. Polar codes - Part II (Guest Lecturer: Ramprasad Saptharishi) Polarization, Arikan's Theorem Ref: [GC13 (parts of Lectures 1, 2, 8, 10 and 11)] 20 Sep 13. Reed Muller codes achieve capacity in the BEC channel (Guest Lecturer: Ramprasad Saptharishi) Ref: [KMSU16, KP16 ]

#### References

The links below point to the actual location of papers at the author's homepages or other electronic repositories and the papers are not reposted locally.

1. [GC13] Venkatesan Guruswami and Mahdi Cheraghchi, 15-859: Information Theory and its applications to ToC, CMU, Spring 2013.
2. [Gop09] Parikshit Gopalan, "A note on Efremenko's Locally Decodable Codes", Elect.\ Colloq.\ on Comput.\ Complexity, TR09-069. 2009.
3. [GRS15] Venkatesan Guruswami, Atri Rudra and Madhu Sudan, "Essential Coding Theory", (draft of book), 2015.
4. [Gur14] Venkatesan Guruswami, "15-859Y: Coding Theory", CMU, Fall 2014.
5. [Kop16] Swastik Kopparty, "198:540: Error Correcting Codes", Rutgers, Spring 2016.
6. [KMSU16] Shrinivas Kudekar, Marco Mondelli, Eren Şaşoğlu, Rüdiger Urbanke, Reed-Muller Codes Achieve Capacity on the Binary Erasure Channel under MAP Decoding, 2016.
7. [KP16] Santhosh Kumar, Henry D. Pfister, Reed-Muller Codes Achieve Capacity on Erasure Channels, 2016.
8. [Luc09] Luca Trevisan, "CS276: Cryptography", Berkeley, Spring 2009.
9. [Sud01] Madhu Sudan, "6.897: Algorithmic Introduction to Coding Theory ", MIT, Fall 2001.
10. [Sud12] Madhu Sudan, "6.S897: Algebra and Computation", MIT, Spring 2012.
11. [Sud13] Madhu Sudan, "6.440: Essential Coding Theory", MIT, Spring 2013.

This page has been accessed at least times since Aug 1, 2016.