Instructor: Dana Moshkovitz
·
Subject requirements and syllabus
Date 
Title 
Reading 
9/8/11 
Hamming’s
Paper: Hamming distance, Hamming Code 
·
Historic background (Shannon and Hamming) 
9/13/11 
Shannon’s Paper:
Shannon entropy, Shannon’s Noisy Coding Theorem 

9/15/11 
Nonexplicit Constructions:
Gilbert, Varshamov 

9/20/11 
Lower Bounds:
Singleton, Hamming, Plotkin and EliasBassalygo Bounds, Johnson Bound 

9/22/11 
Algebraic Codes:
ReedSolomon, ReedMuller, Hadamard, BCH Codes 
·
Madhu’s notes (&
algebra review) 
9/27/11 
Concatenation:
Wozencraft Ensemble, Justensen
Codes, concatenation with hitters 

9/29/11 
AlgebraicGeometry Codes: History
starting Goppa, elementary example improving
ReedMuller, statement of GarciaStichtenoth 

10/4/11 
Linear Programming Bound:
Delsarte’s approach, MacWilliams
Identity, Alon’s proof of a comparable bound. 

10/6/11 
Decoding ReedSolomon and Concatenated
Codes: BerlekampWelch
with variants, generalizations, applications. 

10/11/11 
Columbus Day Weekend 

10/13/11 
List Decoding:
proof of Johnson bound, rate vs. radius 

10/18/11 
List Decoding of ReedSolomon:
Sudan and GuruswamiSudan algorithms 

10/20/11 
Capacityachieving List Decoding: ParvareshVardy,
GuruswamiRudra 

10/25/11 
LDPC Codes:
Gallager, Tanner, SipserSpielman 

10/27/11 
Decoding LDPC Codes:
SipserSpielman 
·
Venkat’s survey:
LDPC codes can achieve channel capacity? 
11/1/11 
No lecture 

11/3/11 
LinearTime Encodable
and Decodable Codes: Spielman 

11/8/11 
Expander Codes:
AlonBrooksNaorNaorRoth (ABNNR), AlonEdmondsLuby, GuruswamiIndyk 

11/10/11 
Locally Decodable Codes:
ReedMuller, Yekhanin’s construction (simpler
presentation) 

11/15/11 
Locally Decodable Codes Lower Bounds:
KatzTrevisan 

11/17/11 
Locally Testable Codes:
BlumLubyRubinfeld
linearity testing, low degree testing 

11/22/11 
Codes in Crypto & Communication
Complexity: hardcore predicates, secret sharing,
communication complexity of equality testing 

11/29/11 
Multiplicity Codes (Madhu):
KoppartySarafYekhanin 
·
KoppartySarafYekhanin paper 
12/1/11 
Codes and Extractors (Madhu) 

12/6/11 
Pesudorandom
Generators From Codes: SudanVadhanTrevisan, NisanWigderson 

12/8/11 
6.440 Projects Presentation I 

12/13/11 
6.440 Projects Presentation II 
1.
Problem Set 1, due September 27, 2011.
2.
Problem Set 2, due October 18, 2011. / A version without hints.
3.
Problem Set 3, due November 22, 2011.
What
are Error Correcting Codes?
Error correcting codes are redundant ways to represent information, so it becomes resilient to bounded amount of error.
Formally, a (binary) encoding is a function E:{0,1}^{k}>{0,1}^{n} that takes k bits of information and encodes them with n bits of redundant information, such that for every two different strings of information x,y, the strings E(x) and E(y) agree (i.e., E(x)_{i}=E(y)_{i}) on not much more than n/2 coordinates.
Hence, even if nearly quarter of the n symbols in the encoding get corrupted, we can still figure out the information!
What
does the Subject Cover?
The subject covers constructions of codes, bounds (e.g., how large should n be as a function of k? What’s the maximal amount of error that can be tolerated?), algorithms for encoding and decoding, and applications of error correcting codes to theoretical computer science.
Why do
Theoretical Computer Scientists Care About Codes?
Error correcting codes are used frequently in complexity, cryptography and algorithms, and are in the heart of some of the central results of theoretical computer science, like:
· Communication complexity: how two players, one with a string x in {0,1}^{k}, and one with a string y in {0,1}^{k}, can probabilistically discover whether x=y by exchanging just one bit!
· Average case vs worst case: how to reduce certain worst case problems, like the permanent, to average case problems.
· Hardness vs Randomness tradeoffs: how to use hard functions to construct pseudorandom generators.
· Hardcore predicates: how to find a Boolean predicate H(x) that is easy to compute given x, but hard to compute from the image of a oneway function f(x).
· The Probabilistically Checkable Proofs (PCP) Theorem: how to convert any math proof to a format that allows probabilistic checking by reading only a constant number of bits.
What are the prerequisites for the subject?
Basic math (discrete math, linear algebra, probability),
algorithms (6.046 or equivalent),
and complexity (6.045 or 6.840 or equivalent).
What
are the subject’s requirements?
Students are asked to solve 4 psets and do a project.
More information?
The best way to know what the subject is going to be like is to take a look at
previous offerings of the subject,
by Madhu Sudan: