CMPT 881 - Error-correcting codes, pseudorandomness, and complexity theory -
Spring'07
Instructor |
Times & dates |
Homeworks |
Lectures |
Relevant links
- Apr 16.
The final grades (as well as the grades for the projects: oral and written)
are now available at the gradebook. You can pick up your projects with my
comments from me (send me an email or drop by my office). Have a good summer!
- Apr 12.
All homework assignments are now graded; the grades are available at the
gradebook.
- Apr 5.
The project presentations will be: Thursday, April 12, at 16:30-18:30, and
Friday, April 13, at 11:30-13:30. Both are in TASC 9204 West.
- Mar 28. Homework 4 (the last one) is now available.
- Mar 15. Solutions to Homework 2 are now posted.
- Mar 14. Homework 3 is now available (see nelow). It is due on March 27.
- Mar 14. The class on Tuesday, March 20, will be in the
morning, 9:30-11:20, in AQ 5007 (original time & place).
- Mar 12. HW 1 is now graded (the grades are available at
gradebook.cs.sfu.ca ). I'll bring the assignments to class tomorrow.
- Mar 5.
The deadline for submitting the assignment is moved to this Thursday
(as asked by a few of you).
- Feb 21. Due to popular demand, Josh will continue next
Tuesday, Feb 27, on the LP bound. It is an optional lecture; just to finish
the material Josh could not cover last time. Still you are very
much encouraged to attend to hear about the LP bound. The lecture will
probably be much less than two hours.
- Feb 17. Solutions to HW 1 are now posted.
- Feb 15.
Next Tuesday, Feb 20, there will be a guest lecture by Josh. The next lecture
after that is on Tue, March 6. Please use this "reading break" to work on your
course projects! (see the potential list of project topics below)
- Feb 10. Homework 2 is now available.
- Jan 19. We will change the class time on Tuesdays. The new
class time will be 4:30-6:20pm, in TASC 2 #8500. Note the new room - it's
in the new bulding right next to TASC 1. So our next class on Tuesday, Jan 23,
will be at the new time in the new room.
- Jan 17. The first homework is now available (see below).
It is due Feb 1.
- Jan 8. The first class is on Tuesday, January 9,
9:30-11:20, in AQ 5007. We may decide to move the class times for
subsequent classes; to be discussed in the first week. (Once we decide
to move the class times, it will be announced here.)
Course description
Course Text: There is no textbook for this
course. Below are a few suggested sources for some of the material
to be covered.
Course webpages, notes, and surveys available online
-
lecture notes on some basics
of algebra by Madhu Sudan (MIT)
- lecture notes
on the Algorithmic Coding Theory taught by Madhu Sudan (MIT)
- lecture
notes from the mini-course on "Error-correcting codes and computational
complexity" taught by Madhu Sudan (MIT) at the 2006 Barbados workshop on
complexity
- course
webpage, including some scribed lectures, for a similar course taught by
Venkat Guruswami (U Washington)
- course
webpage, including some scribed lectures, for a similar course taught by
Luca Trevisan (UC Berkeley); see also the excellent
survey on Coding Theory and Computational Complexity by Luca Trevisan.
- lecture notes for a
course on pseudorandomness taught by Salil Vadhan (Harvard)
- lecture notes
for a course on expander graphs taught by Nati Linial and Avi Wigderson (Hebrew University).
- Derandomizing
complexity classes
an extensive survey on derandomization by Peter Bro Miltersen.
Books
- "Elements of Information Theory" by T.M. Cover and J.A. Thomas
is a standard textbook on information theory.
- "Randomized Algorithms" by R. Motwani and P. Raghavan is an excellent
source on various techniques
for constructing randomized algorithms.
- "Modern Cryptography, Probabilistic Proofs and Pseudorandomness" by
Oded Goldreich has a
survey chapter on pseudorandom generators, which provides an excellent
introduction to the area.
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.).