Harvard University homepage
HARVARD.EDU

Madhu Sudan: Harvard CS 229r: Essential Coding Theory (Spring 2017)

This course may have add additional information including problem sets and solutions. If you need these for teaching a course of your own, please write to Madhu.

General Info

  • Lecturer: Madhu Sudan;  MD 339; email: first name at cs dot harvard dot edu; Office Hours: TuTh 5-6pm (tentative)
  • Lecture Time and Location: TuTh 11:30am-1:00pm in Cruft 309.

Other links for the course

Announcements

  • LECTURE on 02/09/17 CANCELLED!!
  • Please sign up for scribing! Signup instructions and sheet here. Template for scribing here (preamble, lect01.tex).
  • Problem Set 1 (tex, pdf). Due Wednesday 02/08/2017. Canvas link.
  • Problem Set 2 (tex, pdf). Due Wednesday 2/22/2017. Canvas link.
  • Problem Set 3 (tex, pdf). Due Wednesday 3/8/2017. Canvas link.
  • Here is a list of potential projects (or you can suggest your own idea). I will email the editable link and you can edit the sheet to express interest in a project. If you don’t have a partner in mind, it might be good to trawl the sheet for a combination of project+partner.
  • PROJECTS + PRESENTATIONS: Schedule. All presentations will be held in MD 323 on Tuesday, May 2, 2017.

Topics (Tentative), Calendar and Handouts

  • Lecture 01 (Tue. 01/24): Introduction. Hamming’s Paper. Codes, Distance, Examples, Limits and Algorithms. Notes from 2008 (use these notes for technical content; not for grading policy etc.!). Scribe Notes (tex, pdf). Reading [Chapter 1 and Chapter 2 from the text.]
  • Lecture 02 (Thu. 01/26): Shannon’s Theorems. Noiseless coding. Noisy Coding. Shannon Capacity. Notes from 2008. Reading [Chapter 6]. Scribe notes (tex, pdf).
  • Lecture 03 (Tue. 01/31): Converse to Shannon’s theorem. Random codes. Linear codes. Gilbert-Varshamov theorems. Asymptotics of error-correcting codes. Notes from 2008. Reading [Chapter 1 and Chapter 4]. Scribe notes (tex, pdf).
  • Lecture 04 (Thu. 02/02): Simple Impossibility Results for Codes. (Pigeonhole argument, packing argument, geometric arguments). Reading [Chapter 4 and Chapter 8]. Notes from 2008, Scribed notes from 2001. Scribe notes (tex, pdf).
  • Lecture 05 (Tue. 02/07): Finish impossibility results. (Notes from 2008). Algebraic codes: Reed-Solomon codes. Concatenated codes. (Notes from 2008). Readings [Chapter 8, Chapter 5]. Scribe notes (tex, pdf).
  • Lecture 06 (Thu. 02/09): LECTURE CANCELLED due to weather.
  • Lecture 07 (Tue. 02/14): Codes from univariate polynomials contd.: Forney, Justesen. BCH codes. Codes from Multivariate polynomials: Reed-Muller, Hadamard. Notes from 2008 (Reed-Muller etc., BCH). Scribe notes (tex, pdf).
  • Lecture 08 (Thu. 02/16): Dual BCH codes. Algebraic Geometry Codes. Notes from 2013. Scribe notes (tex, pdf).
  • Monday 02/20: Presidents’ Day Holiday
  • Lecture 09 (Tue. 02/21): Algorithmic problems in Coding theory. Decoding Reed-Solomon Codes. Reading materials.
  • Lecture 10 (Thu. 02/23): Decoding Concatenated Codes. Achieving Shannon Capacity. Notes from 2008. Scribe notes (tex, pdf).
  • Lecture 11 (Tue. 02/28): List-decoding: Combinatorics. List-decoding Reed-Solomon Codes. Notes from 2008. Scribe notes (tex, pdf).
  • Lecture 12 (Thu. 03/02): Folded Reed-Solomon Codes and List-decoding. Notes. No scribe notes, but the notes from 2013 should be pretty close to what we did (tex, pdf).
  • Lecture 13 (Tue. 03/07): Graph-theoretic codes (Gallager, Tanner, Sipser-Spielman). Linear time encoding and decoding. Notes from 2008. Scribe notes (tex, pdf).
  • Lecture 14 (Thu. 03/09): Graph-theoretic codes II (Alon-Luby construction, Guruswami-Indyk). Notes. Scribe notes (tex, pdf).
  • Sat. 3/11- Sun 3/19: Spring break
  • Lecture 15 (Tue. 03/21): Polar codes. Introduction to the notion. Encoding + Decoding. References:
  • Lecture 16 (Thu. 03/23): Polar codes. Shannon capacity with polynomial convergence. Notes. Scribe notes (tex, pdf).
  • Lecture 17 (Tue. 03/28): CANCELLED.
  • Lecture 18 (Thu. 03/30): Locality in coding: Introduction, Locally Recoverable Codes. Notes. Scribe notes (tex, pdf).
  • Lecture 19 (Tue. 04/04): Locality in coding: Locally Decodable Codes. Notes. Scribe notes (tex, pdf).
  • Lecture 20 (Thu. 04/06): Locality in Coding: Locally Testable Codes. Notes.
  • Lecture 21 (Tue. 04/11): Local Testability of Tensor Products and Low-degree polynomials. Notes. 
  • Lecture 22 (Thu. 04/13): Codes and derandomization: Limited independence, epsilon-bias, almost independence. Notes.
  • Lecture on Tue 04/18 Guest Lecture by Pritish Kamath. Interactive Coding – I. My notes (part I and part II).
  • Lecture on Tue 04/20 Guest Lecture by Pritish Kamath. Interactive Coding – II. Pritish’s Notes.
  • Lecture 23 (Tue. 04/25): (Last lecture) Codes and complexity: Pseudorandom generation from one-way functions, Hardness amplification. Notes. Scribe notes (tex, pdf).

Reference Materials