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

Time: Mon-Wed 09:30-11:00
Location: A201
Instructor:
Teaching Assistant:

Course Announcement

 Videos Problem Sets Lectures Projects References

#### 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

Potential topics for projects and paper presentation
• 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
• 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.