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

Location: A201
Instructors :
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2016-17/coding//

Course Calendar (Click here to subcribe to the calendar (ical format))

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 several times since Aug 1, 2016.

Prahladh Harsha
Valid HTML 4.01! Valid CSS!