Search | Directories | Reference Tools
UW Home > Discover UW > Student Guide > Course Catalog 

Instructor Class Description

Time Schedule:

Venkatesan Guruswami
CSE 533
Seattle Campus

Advanced Topics in Complexity Theory

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).


The information above is intended to be helpful in choosing courses. Because the instructor may further develop his/her plans for this course, its characteristics are subject to change without notice. In most cases, the official course syllabus will be distributed on the first day of class.
Additional Information
Last Update by Venkatesan Guruswami
Date: 07/24/2006