CS294 - Coding Theory and Complexity


Instructor: Luca Trevisan, luca@cs, 615 Soda Hall, Tel. 642 8006

Classes are Mondays-Wednesdays, 2:30-4:00pm, 405 SODA

Office hours: Tuesdays, 2-3pm or by appointment.


course description

Error-correcting codes and related combinatorial constructs play an important role is several recent (and old) results in complexity theory. In most cases, such as in the Goldreich-Levin hard-core predicate construction, the coding theory interpretation became clear only in retrospect, but then it was essential for further improvements. This course will be about the theory, constructions,  and algorithms for error correcting codes, about applications in complexity theory and in cryptography, and about relations to other combinatorial constructions.

In the first part of the course we will see constructions of Reed-Solomon codes, Reed-Muller codes and Low-weight Parity Check Codes, along with their unique-decoding and list-decoding algorithms. Then we will see "local decoding" and "local checking" algorithms, and their applications to average-case complexity, cryptography, program testing, and probabilistically checkable proofs. In the third part of the course we will explore connections between error-correcting codes and the other three combinatorial  objects that are  ubiquitous in complexity theory: hash functions, randomness extractors and expander graphs.

classes and notes

  1. 8/25 Introduction to error-correcting codes, linear codes, Singleton bound,  Gilbert-Varshamov boud, Reed-Solomon codes, Berlekamp-Welch algorithm. [notes]
  2. 8/27 Alternative view of Reed-Solomon codes, Concatenation, Justenssen codes. [notes]
  3. 9/3 Efficient polynomial multiplication, more on Justenssen codes, Reed-Muller codes, "Hadamard" code. [notes]
  4. 9/8 The Plotkin bound; Decoding concatenated codes.  [notes]
  5. 9/10 More on decoding concatenated codes; List decoding; Johnson bound [notes (kamalika)]
  6. 9/15 List-decoding of Reed-Solomon codes and concatenated codes [notes]
  7. 9/17 Unique-decoding of low-weight parity-check codes [notes]
  8. 9/22 More expander-based constructions and their unique decoding algorithms [notes]
  9. 9/24 Unique decoding from errors and erasures, and list-decoding of expander-based codes [notes (boriska)]
  10. 9/29 List-decoding of expander-based codes  (construction with rate epsilon2) [notes (james)]
  11. 10/1 List-decoding of expander-based codes (construction with rate epsilon) [notes]
  12. 10/6 List-decoding of expander-based codes (linear time decoding) [notes (david)]
  13. 10/8 Locally decodable codes (constructions with unique decoding, large query complexity) [notes ?]
    10/13 FOCS, no class
  14. 10/15 Locally decodable codes (constructions with unique decoding, small query complexity) [notes]
  15. 10/20 Locally decodable codes (lower bounds for q queries) [notes]
    10/22 canceled
  16. 10/27 Locally decodable codes (lower bound for 2 queries, linear codes)  [notes (boriska)]
  17. 10/29 Locally decodable codes (lower bound for 2 queries, general codes) [notes]
  18. 11/3  Locally decodable codes (Goldreich-Levin: list-decoding of Hadamard codes) [notes (Luca)]
  19. 11/5 Locally decodable codes (Use of Goldreich-Levin for hard-core predicates and learning) [notes]
  20. 11/10 Locally decodable codes (Other hard-core predicates using list-decoding) [notes]
  21. 11/12 Locally decodable codes (List-decoding of Reed-Muller codes and average-case complexity) [notes (Luca)]
  22. 11/17 Locally testable codes and PCP (definition of PCP, LTC, assignment tester) [notes (Luca)]
  23.  11/19  Locally testable codes and PCP (linearity testing and exponential-length PCP) [notes (Daniel)]
  24. 11/24 Locally testable codes and PCP (Low-degree tests, PCP/AT with polylog query complexity and large alphabet, part 1) [notes]
  25. 11/26 Locally testable codes and PCP (PCP/AT with polylog query complexity and large  alphabet, part 2)
  26. 12/1 Locally testable codes and PCP (aggregation) [notes]
  27. 12/3 Locally testable codes and PCP (composition and PCP theorem) [notes (Hoeteck)]

tentative syllabus

We will probably only cover a subset of the following topics



combinatorial constructions


related courses