CSS.318.1: Coding Theory - Monsoon Semester (2022-23)

Time: Mon-Wed 09:30-11:00
Location: A201
Teaching Assistant:
Homepage: https://www.tifr.res.in/~prahladh/teaching/2022-23/coding/

Course Announcement

Videos Problem Sets Lectures Projects References

Online Videos of Lectures

Problem Sets

  1. PS1 [(out: 12 Sep, due: 26 Sep)]
  2. PS2 [(out: 3 Oct, due: 17 Oct)]
  3. PS3 [(out: 26 Oct, due: 9 Nov)]
  4. PS4 [(out: 21 Nov, due: 9 Dec)]
  5. Final Exam [(12 Dec)]


Collated Lecture Notes [ pdf (246 pages, handwritten) ]

  1. Introduction and Hamming's Problem (Aug 29)
    Administrivia; Examples (guessing hats, secret sharing, pool testing); Hamming's Problem
    [Notes]; Ref: [Sud08 (Lec 1), NYtimes Hat Puzzle, VV Coding Theory Trailer]
  2. Coding theory basics (Sep 2)
    Coding theory basics; Hamming/packing bound,linear codes, Hamming code
    [Notes]; Ref: [Sud08 (Lec 1), Gur14 (Lec 1)]
  3. Shannon's Coding theorem (Sep 5)
    Shannon's model of communication, Channels (BSC, BEC), Shannon, coding theorem for BSC
    [Notes]; Ref: [Sud08 (Lec 2), GRS (Chap. 7)]
  4. What can and cannot be done (Sep 7)
    Shannon's converse coding theorem for BSC; Hamming bound in asymptotic notation, Gilbert-Varshamov bound
    [Notes]; Ref: [GRS (Chap 6.3.1, 4.1, 4.2)]
  5. Bounds on Codes (Sep 14)
    Singleton bound, Plotkin bound, Elias-Bassalygo bound; Johnson radius; Survey on the coding bounds so far
    [Notes]; Ref: [Sud08 (Lec. 4)]
  6. Reed-Solomon Code: The one code to rule them all (Sep 16)
    Reed-Solomon code, degree mantra, MDS codes, a primer on Finite fields, dual of RS codes
    [Notes]; Ref: [Sud08 (Lec. 5), GRS (Chap. 5)]
  7. BCH codes (Sep 19)
    BCH codes, Trace map, dual of Reed-Solomon codes, Dual-BCH codes
    [Notes]; Ref: [Kop16 (Lec. 5)]
  8. Reed-Muller Codes (Sep 21)
    Recap of Elias-Bassalygo bound and Johnson radius; Reed-Muller codes, Two settings (low-degree and binary field), Generalized SZ Lemma, Dual of RM codes
    [Notes]; Ref: [Sud08 (Lec. 4), GRS (Chap. 9)]
  9. Unique-decoding of Reed-Solomon Codes (Sep 26)
    Gemmell-Sudan presentation of the Welch-Berlekamp unique-decoding algorithm for RS codes, Peterson, Berlekamp-Massey algorithms
    [Notes]; Ref: [Sud08 (Lec. 10), Gur14 (Notes. 7)]
  10. Code Concatenation (Sep 28)
    Forney's code concatenation, Zyablov's bound, Justesen codes, Wozencraft's ensemble
    [Notes]; Ref: [Sud08 (Lec. 7), GRS (Chap. 10)]
  11. Decoding Concatenated Codes (Oct 3)
    Vanilla decoding concatenated codes, Acchieving BSC capacity, intro to Forney's GMD decoding
    [Notes]; Ref: [Sud08 (Lec. 11)]
  12. GMD Decoding (Oct 10)
    Forney's GMD decoding; Graph-based codes (Gallagher, Tanner, Sipser-Spielman), Expander graphs
    [Notes]; Ref: [GRS (Chap. 13), Sud08 (Lec. 17)]
  13. Expander Codes (Oct 12)
    Unique expansion, Tanner codes, Sipser-Spielman, linear-time decodable codes
    [Notes]; Ref: [GRS (Chap. 11), Sud08 (Lec. 17)]
  14. Distance Amplification via expanders (Oct 17)
    Linear-time decodable codes (Sipser-Spielman, Zemor), Expander Mixing Lemma, Distance Amplification (Alon-Bruck-Naor-Naor-Roth and Alon-Edmonds-Luby)
    [Notes]; Ref: [Gur14 (Notes. 8), Kop16 (Lec. 6-7)]
  15. Combinatorics of List-decoding (Oct 21)
    Introduction to list-decoding; limits on rates of list-decodable codes, Johnson radius
    [Notes]; Ref: [Sud08 (Lec. 12)]
  16. List-decoding of Reed-Solomon Codes (Oct 26)
    Sudan's algorithm for list-decoding Reed-Solomon codes, Role of multiplicities, Guruswami-Sudan's improvement
    [Notes]; Ref: [GRS (Chap. 17)]
  17. Local Decoding of the Hadamard Code (Oct 31)
    Local unique-decoding and list-decoding of the Hadamard code; sub-linear time algorithms, Goldreich-Levin algorithm
    [Notes]; Ref: [Tre09 (Chap. 9)]
  18. Decoding Reed-Muller codes (Nov 2)
    Reed's majority decoder; Local decoder; Pellikaan-Wu reduction to Reed-Solomon codes
    [Notes]; Ref: [GRS (Chap. 15)]
  19. Locally Decodable Codes (Nov 9)
    Locally decodable codes (definition and examples); Efremenko's consruction using matching vectore codes
    [Notes]; Ref: [Har16 (Lec. 9-10) (notes, Gop09, Sud12 (Lec. 23-24)]
  20. Locally Recoverable Codes (Nov 11)
    Locally recoverable codes (message and codeword recoverable), Singleton-like bound,Tamo-Barg LRC construction
    [Notes]; Ref: [GRS (Chap. 19)]
  21. Polar Codes - I (Nov 14)
    Fully-constructive version of Shannon's theorem, linear compression scheme, polarizing matrix, Arikan's construction
    [Notes]; Ref: [GRS (Chap. 12)]
  22. Polar Codes - II (Nov 16)
    Arikan's martingale, local polarization, strong polarization
    [Notes]; Ref: [GRS (Chap. 12)]
  23. Multiplicity Codes - I (Nov 21)
    Hasse Derivatives, Multiplicity Codes -- definition, distance and rate of univariate multiplicity codes
    [Notes]; Ref: [Kop15]
  24. Multiplicity Codes - II (Nov 23)
    List-decoding univariate multiplicity codes
    [Notes]; Ref: [Kop15]
  25. Multiplicity Codes - III (Nov 28)
    Univariate multiplicity codes: list-decoding up to capacity; lossless unbalanced expanders
    [Notes]; Ref: [Kop15, KT22]
  26. Multiplicity Codes - IV (Dec 5)
    Multivariate multiplicicty codes; multiplicity Schwartz-Zippel Lemma; LDC with rate close to 1
    [Notes]; Ref: [Kop13]


Potential topics for projects and paper presentation


Students taking the course for credit will be expected to:


Parikshit Gopalan, "A note on Efremenko's Locally Decodable Codes", Elect. Colloq. on Comput. Complexity, TR09-069. 2009.
Venkatesan Guruswami, Atri Rudra and Madhu Sudan, "Essential Coding Theory", (draft of book), 2022.
Venkatesan Guruswami, "15-859Y: Coding Theory", CMU, Fall 2014.
Prahladh Harsha, "A mini course on Coding Theory - An Algorithmic Viewpoint", TIFR, Monsoon 2016.
Swastik Kopparty, Some remarks on multiplicity codes, Discrete Geometry and Algebraic Combinatorics 2013
Swastik Kopparty, List-Decoding Multiplicity Codes. Theory Comput. 11: 149-182. 2015.
Swastik Kopparty, "198:540: Error Correcting Codes", Rutgers, Spring 2016.
Itay Kalev and Amnon TaShma, Unbalanced Expanders from Multiplicity Codes, RANDOM 2022.
Tom Richardson and RĂ¼diger Urbanke, "Modern Coding Theory", Cambridge University Press, 2008.
Madhu Sudan, "6.440: Essential Coding Theory", MIT, Spring 2008.
Madhu Sudan, "6.S897: Algebra and Computation", MIT, Spring 2012.
Madhu Sudan, "6.440: Essential Coding Theory", MIT, Spring 2013.
Luca Trevisan, "CS276: Cryptography", Berkeley, Spring 2009.

Previous avatars of this course: 2016

This page has been accessed at least several times since 15 Aug, 2022.

Prahladh Harsha