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

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

Course Announcement

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)]

Lectures

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]

Projects

• Delsarte's linear programming bound (MRRW)
• Weil bounds for distance of dual-BCH codes
• Locally Decodable Codes (Katz-Trevisan and DeWolf-Kerenedis)
• Maximal Recoverable Codes
• MDS and GM-MDS conjecture
• Local list-decoding of RM codes (q=2, r=2)
• Lossless expander construction (Guruswami-Umans-Vadhan or Kalev-TaShma)
• RM codes achieve capacity for every BMS channel
• Upper bound for deletion codes
• Codes for interactive communication
• TaShma's epsilon-biased spaces construction and their decoding
• Improved distance for expander codes

Requirements

Students taking the course for credit will be expected to:

• Do problem sets (approx 1 pset every 2-3 weeks)
• Project / Paper Presentation / Final Exam
• Participate actively in class
• Grading Policy:
  • Problems Sets - 75% (best 3 of 4 psets will contribute towards grade)
  • A total of 14 days extra-time that can be distributed across psets
  • Project / Paper Presentation / Final Exam -- 25%

References

[Gop09]

Parikshit Gopalan, "A note on Efremenko's Locally Decodable Codes", Elect. Colloq. on Comput. Complexity, TR09-069. 2009.

[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.

[Kop13]

Swastik Kopparty, Some remarks on multiplicity codes, Discrete Geometry and Algebraic Combinatorics 2013

[Kop15]

Swastik Kopparty, List-Decoding Multiplicity Codes. Theory Comput. 11: 149-182. 2015.

[Kop16]

Swastik Kopparty, "198:540: Error Correcting Codes", Rutgers, Spring 2016.

[KT22]

Itay Kalev and Amnon TaShma, Unbalanced Expanders from Multiplicity Codes, RANDOM 2022.

[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.

[Sud12]

Madhu Sudan, "6.S897: Algebra and Computation", MIT, Spring 2012.

[Sud13]

Madhu Sudan, "6.440: Essential Coding Theory", MIT, Spring 2013.

[Tre09]

Luca Trevisan, "CS276: Cryptography", Berkeley, Spring 2009.

Previous avatars of this course: 2016

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