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

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

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

**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]**Coding theory basics**(Sep 2)

Coding theory basics; Hamming/packing bound,linear codes, Hamming code

[Notes]; Ref: [Sud08 (Lec 1), Gur14 (Lec 1)]**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)]**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)]**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)]**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)]**BCH codes**(Sep 19)

BCH codes, Trace map, dual of Reed-Solomon codes, Dual-BCH codes

[Notes]; Ref: [Kop16 (Lec. 5)]**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)]**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)]**Code Concatenation**(Sep 28)

Forney's code concatenation, Zyablov's bound, Justesen codes, Wozencraft's ensemble

[Notes]; Ref: [Sud08 (Lec. 7), GRS (Chap. 10)]**Decoding Concatenated Codes**(Oct 3)

Vanilla decoding concatenated codes, Acchieving BSC capacity, intro to Forney's GMD decoding

[Notes]; Ref: [Sud08 (Lec. 11)]**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)]**Expander Codes**(Oct 12)

Unique expansion, Tanner codes, Sipser-Spielman, linear-time decodable codes

[Notes]; Ref: [GRS (Chap. 11), Sud08 (Lec. 17)]**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)]**Combinatorics of List-decoding**(Oct 21)

Introduction to list-decoding; limits on rates of list-decodable codes, Johnson radius

[Notes]; Ref: [Sud08 (Lec. 12)]**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)]**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)]**Decoding Reed-Muller codes**(Nov 2)

Reed's majority decoder; Local decoder; Pellikaan-Wu reduction to Reed-Solomon codes

[Notes]; Ref: [GRS (Chap. 15)]**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)]**Locally Recoverable Codes**(Nov 11)

Locally recoverable codes (message and codeword recoverable), Singleton-like bound,Tamo-Barg LRC construction

[Notes]; Ref: [GRS (Chap. 19)]**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)]**Polar Codes - II**(Nov 16)

Arikan's martingale, local polarization, strong polarization

[Notes]; Ref: [GRS (Chap. 12)]**Multiplicity Codes - I**(Nov 21)

Hasse Derivatives, Multiplicity Codes -- definition, distance and rate of univariate multiplicity codes

[Notes]; Ref: [Kop15]**Multiplicity Codes - II**(Nov 23)

List-decoding univariate multiplicity codes

[Notes]; Ref: [Kop15]**Multiplicity Codes - III**(Nov 28)

Univariate multiplicity codes: list-decoding up to capacity; lossless unbalanced expanders

[Notes]; Ref: [Kop15, KT22]**Multiplicity Codes - IV**(Dec 5)

Multivariate multiplicicty codes; multiplicity Schwartz-Zippel Lemma; LDC with rate close to 1

[Notes]; Ref: [Kop13]

- 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

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%

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

Prahladh Harsha |