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
- PS1 [(out: 30 Jan, due: 13 Feb)]
- PS2 [(out: 19 Feb, due: 05 Mar)]
- PS3 [(out: 12 Mar, due: 26 Mar)]
- 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]
- 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)]
- 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)]
- 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)]
- 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)]
- 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)]
- 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)]
- 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)]
- BCH Codes (13 Feb)
BCH Codes, BCH codes almost satisfy Hamming bound, Trace function, dual-BCH codes
Ref: [Har22 (Lec. 7), Kop16 (Lec. 5)]
- 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)]
- 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)]
- 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)]
- Decoding Concatenated Codes (27 Feb)
Vanilla decoding concatenated codes, Acchieving BSC capacity
Ref: [Har22 (Lec. 11), Sud08 (Lec. 11)]
- GMD Decoding (27 Feb)
Forney's GMD decoding
Ref: [Har22 (Lec. 12), GRS (Chap. 13), Sud08 (Lec. 11)]
- 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)]
- 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)]
- 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)]
- List decoding to capacity (12 Mar)
Univariate multiplicity codes - definition and properties, list decoding algorithm
Ref: [GW13]
- List decoding to capacity contd. (19 Mar)
Univariate multiplicity codes - list decoding algorithm, pruning the list size to a constant
Ref: [GW13, Tamo23]
- 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)]
- 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)]
- 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)]
- 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)]
- 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)]
- Multivariate multiplicity codes (23 Apr)
Multivariate multiplicity codes - definitions, and local decoding algorithm
- Dual BCH codes (23 Apr)
Distance of Dual BCH codes - Bombieri's proof
- Student presentations (30 Apr)
Potential topics for projects and paper presentation
- Delsarte's linear programming bound (MRRW)
- Subspace polynomials and list decoding of Reed-Solomon codes (Ben-Sasson-Kopparty-Radhakrishnan)
- Limits to list decoding Reed-Solomon codes (Guruswami-Rudra)
- Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields (Alrabiah-Guruswami-Li)
- Linear time endoable and list decodable codes (Guruswami-Indyk)
- Locally Decodable Codes (Katz-Trevisan and DeWolf-Kerenedis)
- Private information retrieval (Woodruff-Yekhanin, Dvir-Gopi)
- 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
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 - 72% (best n-1 of n psets will contribute
towards grade)
- A total of 14 days extra-time that can be distributed across
psets
- Class Participation - 8%
- Project / Paper Presentation / Final Exam -- 20%
- [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
times since 15 Jan, 2024.