CSS.318.1: Coding Theory - Winter/Summer Semester (2023-24)

Time: Tues 11:30-13:00 and 14:00-15:30
Location: A201
Instructor: and
Homepage: https://www.tcs.tifr.res.in/~prahladh/teaching/2023-24/coding/

Course Announcement

Lectures Projects References

Problem Sets

  1. PS1 [(out: 30 Jan, due: 13 Feb)]
  2. PS2 [(out: 19 Feb, due: 05 Mar)]
  3. PS3 [(out: 12 Mar, due: 26 Mar)]

Lectures

  1. Introduction and Hamming's Problem (16 Jan)
    Administrivia; Examples (guessing hats, secret sharing, pool testing); Hamming's Problem
    Ref: [Har22 (Lec 1), Sud08 (Lec 1), NYtimes Hat Puzzle, VV Coding Theory Trailer]
  2. Coding theory basics (16 Jan)
    Coding theory basics; Hamming/packing bound, finite fields, linear codes
    Primer on finite fields by Guruswami, Ref: [Har22 (Lec 2), Sud08 (Lec 1), Gur14 (Lec 1)]
  3. Hamming and Shannon's questions (25 Jan)
    Hamming codes; Shannon's model of communication, Channels (BSC, BEC), Shannon's source and channel coding theorems
    Ref: [Har22 (Lec 2-3), Sud08 (Lec 1-2), GRS (Chap. 6)]
  4. Shannon's Coding theorem for BSC (25 Jan)
    Binary entropy function; Shannon's coding theorem and converse theorem for BSC
    Ref: [Har22 (Lec 3-4), Sud08 (Lec 2), GRS (Chap. 6)]
  5. What can and cannot be done (30 Jan)
    Hamming bound in asymptotic notation, Gilbert-Varshamov bound, Singleton bound
    Ref: [Har22 (Lec 4-5), GRS (Chap 4.1, 4.2, 4.3)]
  6. Bounds on Codes (30 Jan)
    Plotkin bound, Elias-Bassalygo bound; Johnson radius; Survey on the coding bounds so far
    Ref: [Har22 (Lec 5), Sud08 (Lec. 4), GRS (Chap 4.4, 8.1, 7.3)]
  7. Reed-Solomon Code: The one code to rule them all (6 Feb)
    Reed-Solomon code, degree mantra, MDS codes, a primer on Finite fields
    Ref: [Har22 (Lec 6), Sud08 (Lec. 5), GRS (Chap. 5)]
  8. Reed-Solomon and BCH codes (6 Feb)
    Primer on finite fields (contd), Proof of Degree Mantra, Dual of Reed-Solomon codes, BCH codes,
    Ref: [Har22 (Lec. 6-7), Sud08 (Lec. 5), GRS (Chap. 5), Kop16 (Lec. 5)]
  9. BCH Codes (13 Feb)
    BCH Codes, BCH codes almost satisfy Hamming bound, Trace function, dual-BCH codes
    Ref: [Har22 (Lec. 7), Kop16 (Lec. 5)]
  10. Reed-Muller Codes (13 Feb)
    Reed-Muller codes, Two settings (low-degree and binary field), Generalized SZ Lemma, Dual of RM codes
    Ref: [Har22 (Lec. 8) Sud08 (Lec. 4), GRS (Chap. 9)]
  11. Unique-decoding of Reed-Solomon Codes (20 Feb)
    RM codes as subfield subcodes of RS; Gemmell-Sudan presentation of the Welch-Berlekamp unique-decoding algorithm for RS codes
    Ref: [Har22 (Lec. 15 and 9), GRS (Chap. 15), Sud08 (Lec. 10), Gur14 (Notes. 7)]
  12. Code Concatenation (20 Feb)
    Forney's code concatenation, Zyablov's bound, Justesen codes, Wozencraft's ensemble
    Ref: [Har22 (Lec. 10), Sud08 (Lec. 7), GRS (Chap. 10)]
  13. Decoding Concatenated Codes (27 Feb)
    Vanilla decoding concatenated codes, Acchieving BSC capacity
    Ref: [Har22 (Lec. 11), Sud08 (Lec. 11)]
  14. GMD Decoding (27 Feb)
    Forney's GMD decoding
    Ref: [Har22 (Lec. 12), GRS (Chap. 13), Sud08 (Lec. 11)]
  15. Combinatorics of List-decoding (05 Mar)
    Introduction to list-decoding; limits on rates of list-decodable codes, Johnson radius
    Ref: [Har22 (Lec. 15), Sud08 (Lec. 12)]
  16. List-decoding of Reed-Solomon Codes (05 Mar)
    Sudan's algorithm for list-decoding Reed-Solomon codes, Role of multiplicities, Guruswami-Sudan's improvement
    Ref: [Har22 (Lec. 16), GRS (Chap. 17)]
  17. List-decoding of Reed-Solomon Codes contd. (12 Mar)
    Guruswami-Sudan's algorithm, computing roots of bivariates over finite fields
    Ref: [Har22 (Lec. 16), GRS (Chap. 17)]
  18. List decoding to capacity (12 Mar)
    Univariate multiplicity codes - definition and properties, list decoding algorithm
    Ref: [GW13]
  19. List decoding to capacity contd. (19 Mar)
    Univariate multiplicity codes - list decoding algorithm, pruning the list size to a constant
    Ref: [GW13, Tamo23]
  20. Expander Codes (19 Mar)
    Codes based on expanders - (Tanner, Sipser-Spielman), definition and properties, linear-time decoding
    [Notes]; Ref: [GRS (Chap. 11), Sud08 (Lec. 17)]
  21. Expander Codes contd. (02 Apr)
    Codes based on expanders - (Tanner, Sipser-Spielman), definition and properties, linear-time decoding
    [Notes]; Ref: [GRS (Chap. 11), Sud08 (Lec. 17)]
  22. Distance Amplification via expanders (02 Apr)
    Distance Amplification (Alon-Bruck-Naor-Naor-Roth and Alon-Edmonds-Luby)
    [Notes]; Ref: [Gur14 (Notes. 8), Kop16 (Lec. 6-7)]
  23. Locally Decodable Codes (16 Apr)
    Locally decodable codes (definition and examples); Local decoding of Hadamard codes, Reed-Muller codes
    [Notes]; Ref: [Har16, Gop09, Sud12 (Lec. 23-24)]
  24. Matching vector codes (16 Apr)
    Matching vector codes - definition, properties and local decoding algorithm, construction of matching vector families
    [Notes]; Ref: [Har16, Gop09, Sud12 (Lec. 23-24)]
  25. Multivariate multiplicity codes (23 Apr)
    Multivariate multiplicity codes - definitions, and local decoding algorithm
  26. Dual BCH codes (23 Apr)
    Distance of Dual BCH codes - Bombieri's proof
  27. Student presentations (30 Apr)

Projects

Potential topics for projects and paper presentation

Requirements

Students taking the course for credit will be expected to:

References

[GRS]
Venkatesan Guruswami, Atri Rudra and Madhu Sudan, "Essential Coding Theory", (draft of book), 2022.
[Gur14]
Venkatesan Guruswami, "15-859Y: Coding Theory", CMU, Fall 2014.
[Har16]
Prahladh Harsha, "A mini course on Coding Theory - An Algorithmic Viewpoint", TIFR, Monsoon 2016.
[Har22]
Prahladh Harsha, "CSS.318.1: Coding Theory", TIFR, Monsoon 2022.
[Kop16]
Swastik Kopparty, "198:540: Error Correcting Codes", Rutgers, Spring 2016.
[RU08]
Tom Richardson and Rüdiger Urbanke, "Modern Coding Theory", Cambridge University Press, 2008.
[Sud08]
Madhu Sudan, "6.440: Essential Coding Theory", MIT, Spring 2008.
[Sud13]
Madhu Sudan, "6.440: Essential Coding Theory", MIT, Spring 2013.

This page has been accessed at least several times since 15 Jan, 2024.

Prahladh Harsha