Time Schedule:
Venkatesan Guruswami
CSE 533
Seattle Campus
An in-depth study of advanced topics in computational complexity. Prerequisite: CSE major.
Class description
Error-correcting codes play an important role in many areas of science and engineering. In this course, we will study the theory of error-correcting codes exclusively in the context of "channel coding" problem: We want to transmit a message across a noisy communication channel so that the receiver can determine this message despite the adverse effects of the channel.
Starting from the basics of coding theory and some of the classic theorems, constructions and algorithms of the subject, the course will discuss recent progress on error-correction algorithms for both stochastic and adversarial (worst-case) models of noise.
List of potential topics (actual topics discussed will be a subset depending on time):
* Shannon coding theorem * Noise models (worst-case, stochastic) * Basics of coding theory (definitions, combinatorial bounds,etc.) * Classical code constructions (algebraic, LDPC, concatenated, etc.) * Reed-Solomon decoding and applications * Belief progagation decoding (of LDPC codes, LT codes) * Expander codes and their decoding * List decoding; achieving "list decoding capacity" * Convolutional coding
Target audience: interested graduate and advanced undergraduate students of CSE, electrical engineering, and mathematics.
Student learning goals
General method of instruction
Classroom lectures on whiteboard
Recommended preparation
Mathematical maturity is the main prerequisite for this class; familiarity with the basics of probability, algebra, and analysis of algorithms is helpful.
Class assignments and grading
Coursework will include taking scribe notes and doing one or two problem sets.
Grades wil be based on quality of scribe notes, class participation, and performance on the problem sets (of which there will be one or two).
