Classes are Mondays-Wednesdays, 2:30-4:00pm, 405 SODA
Office hours: Tuesdays, 2-3pm or by appointment.
Requirements:
attendance
scribing notes for two or more lectures
final project
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
8/25 Introduction to error-correcting codes, linear codes, Singleton
bound, Gilbert-Varshamov boud, Reed-Solomon codes, Berlekamp-Welch
algorithm.
[notes]
8/27 Alternative view of Reed-Solomon codes, Concatenation, Justenssen
codes. [notes]
9/3 Efficient polynomial multiplication, more on Justenssen codes,
Reed-Muller codes, "Hadamard" code. [notes]
9/8 The Plotkin bound; Decoding concatenated codes. [notes]
9/10 More on decoding concatenated codes; List decoding; Johnson
bound [notes (kamalika)]
9/15 List-decoding of Reed-Solomon codes and concatenated codes [notes]
9/17 Unique-decoding of low-weight parity-check codes [notes]
9/22 More expander-based constructions and their unique decoding
algorithms [notes]
9/24 Unique decoding from errors and erasures, and list-decoding of expander-based codes
[notes (boriska)]
9/29 List-decoding of expander-based codes (construction with rate
epsilon2) [notes (james)]
10/1 List-decoding of expander-based codes (construction with rate
epsilon) [notes]
10/6 List-decoding of expander-based codes (linear time decoding) [notes (david)]
10/8 Locally decodable codes (constructions with unique decoding, large
query complexity) [notes
?]
10/13 FOCS, no class
10/15 Locally decodable codes (constructions with unique decoding, small
query complexity) [notes]