Instructor:
Valentine Kabanets (kabanets@cs.sfu.ca), Office:
TASC I #8011
-
Lectures: Tue 16:30-18:20 in TASC 2 #8500, and
Thu 10:30-11:20 in AQ 5007. Note the new time & place for Tuesdays!
-
Office Hours: Tue 2-3 in TASC 1 #8011 (my office), or by appointment
(please email me to set it up).
Important dates
-
Assignments due: Assignment 4 is due April 5
For a course project, you would need to choose a topic in coding (or its
applications
to complexity/pseudorandomness), do some research on the topic, and then write
up the results of your research (in at most 10 pages), plus give an oral
presentation
in class (about 30 min). For your research on the chosen topic, you may want to
read a survey (if you can find it). Plus, you must read and understand at least
one research paper on that topic. (It may be the most recent paper, or the most
influential,
or the only one you could find ;-), ...). Think of this project as a mini-depth
oral
exam.
For your write-up, you may use the survey (or a number of papers you've
looked at) for a general discussion and the general context. Then you should
focus on the research paper you have chosen for the project, and give a summary
of the results/techniques there. Place the research results in that paper in the
context of the whole area. State the main remaining open questions in the area.
List of potential topics [
txt ]
- Jan 9: Applications of
coding to Complexity (PCP theorem), Cryptography (secret sharing,
hardcore bit), Pseudorandomness (expander graphs, undirected
st-connectivity in deterministic logspace); Founders of coding theory:
Shannon and Hamming
-
Jan 11: Shannon's Channel Theorems: source coding (Shannon's
coding) and noisy channel coding; prefix-free codes and Kraft's
Inequality; McMillan's Inequality; the channel capacity.
-
Jan 16: Shannon's Channel Coding Theorem (for Binary Symmetric
Channels, and for Discrete Memoryless Channels); Hamming's worst-case
error model; e-error detecting codes; t-error-correcting codes; the
minimum distance of a code; (n,k,d)_q - codes; simple codes of
distance d=1 and d=2.
-
Jan 18: Linear codes: [n,k,d]_q-codes; generator matrix and
parity check matrices; min distance of a linear code; Hamming's code
of min distance d=3 (given by the parity check matrix); going from
distance d to d+1 for any odd d.
-
Jan 23: Hamming codes: construction (finished); systematic
encoders; optimality of the Hamming code; the Hamming (sphere packing)
bound; Hamming's bound vs. Shannon's Channel Coding Theorem; the
Gilbert-Varshamov (random code) bound; Reed-Solomon codes RS_{q,n,k}:
definitions and properties ([n,k,n-k+1]_q-codes of min distance
exactly n-k+1); the Singleton bound.
-
Jan 25: General decoding problem (NP-hardness of the Nearest
Codeword problem); Decoding Reed-Solomon codes (unambiguous case) via
the Welch-Berlekamp algorithm.
-
Jan 30: Application of Reed-Solomon codes (CDs and DVDs); q-ary
BCH codes (as subfield subcodes of Reed-Solomon codes): definition & a
lower bound on the dimension; Reed-Muller (multivariate polynomial)
codes.
-
Feb 1: Reed-Muller (RM) codes (cont'd); [n, log 2n, n/2]_2
Hadamard code (a special case of RM code); Unambiguous decoding of
Hadamard codes from < 1/4
fraction of errors; three versions of the Schwartz-Zippel lemma (bounding the
number of zeros of a multivariate polynomial) used in the min distance
analysis for RM codes.
-
Feb 6: Asymptotically good families of codes; Forney's "Code
Concatenation" operation; Explicit construction of an asymptotically
good family of codes using the code concatenation: the Zyablov bound;
Wozencraft's ensemble; Justesen's (very explicit) construction of
asymptotically good codes over the binary (q-ary) alphabet.
-
Feb 8: Decoding concatenated codes from up to
distance/4 of errors; Decoding RS concatenated with any
unambiguously decodable code from up to distance/2 of errors;
Decoding from erasures and errors for RS code.
-
Feb 13: Forney's Generalized Minimum Distance Decoding
algorithm (to correct min distance/2 of errors in concatenated codes);
polynomial-time encodable/decodable code achieving Shannon's rate
1-H(p)-eps for BSC(p).
-
Feb 15: Applications of codes to derandomization: d-wise
independent sample spaces of n-bit strings (of size n^{d/2}) from BCH
codes; the matching lower bound on the sample space size; almost
d-wise independent sample spaces (from Reed-Solomon concat. Hadamard).
- Feb 20: [guest lecture by Josh Buresh-Oppenheim]
epsilon-biased sample spaces and almost k-wise independence (cont'd);
the Plotkin bound.
- Feb 27: [guest lecture by Josh
Buresh-Oppenheim] the Linear Programming bound.
- Mar 6: List Decodability: List-Decoding Radius of a code; existence of
good list-decodable codes by the Zyablov-Pinsker theorem; the Johnson
bound; the Elias-Bassalygo bound.
- Mar 8: The Zyablov
& Pinsker Theorem (closer look); List decodability of the Hadamard
code: the information-theoretic upper bound on the list size (using
Discrete Fourier analysis).
- Mar 13: The Goldreich-Levin algorithm for list decoding the
Hadamard code; an application to cryptography: a Hardcore Predicate
for a one-way permutation from the Hadamard code (or any other
efficiently list-decodable binary code).
- Mar 15: List Decoding Reed-Solomon code up to (1-\sqrt{rate})
fraction of errors (matching the Johnson bound for RS codes): Sudan's algorithm.
- Mar 20: Unambiguous (Local) Decoding of Reed-Muller code
(of m-variate degree d polynomials over F_q) up to O(1/d) and up to
O(1) fraction of errors (for q> Omega(d)) in randomized time
poly(m,d,log q), using Implicit Representation.
- Mar 22: List-Decoding RM codes.
- Mar 27: Locally
List-Decodable binary codes; Hardness amplification of Boolean
functions using codes; Expander-based error-correcting codes of Sipser
and Spielman.
- Mar 29: Analysis of the Sipser&Spielman linear-time
decoding algorithm for their expander-based binary linear code
(correcting a constant fraction of errors); Spielman's linear-time
encodable and linear-time decodable binary codes.
- Apr 3 : Locally Testable codes (Hadamard code and Quadratic function
code); NP in PCP[poly n, O(1)]; overview of Dinur's proof of the PCP Theorem.
- Apr 5 : Review: Shannon vs. Hamming vs. Elias; Bounds on codes
(negative: Singleton, Plotkin, Hamming, Elias-Bassalygo, LP; positive:
Gilbert-Varshamov, Zyablov&Pinsker, Johnson); Codes: polynomial-based (Reed-Solomon/Reed-Muller,
BCH, Algebraic Geometry), graph-based (Sipser&Spielman, Spielman,
Alon,Bruck,Naor,Naor,Roth, Guruswami&Indyk); Algorithms (for decoding);
Applications: codes of weight (1/2 +- eps) --> expanders,
eps-biased sample spaces; binary efficiently list-decodable
codes --> hardcore predicate (PRG from one-way permutation);
locally list-decodable binary codes --> hardness
amplification (conditional derandomization of BPP);
locally testable codes --> PCP Theorem; many more connections
not explored in the course due to lack of time (e.g., list-decodable codes
and extractors, quantum error-correction, etc.).