Course title:

Codes and pseudorandom objects: Constructions and Interconnections

3 credits, graduate "special topics" class.

Meeting time: MW 2:00-3:20, EE-042

-------------------------------------------------------
Course Description:

Error-correcting codes are combinatorial objects used to cope with the
problem of reliable communication of information over a noisy
channel. Expanders are sparse yet highly connected graphs with certain
additional "pseudorandom" properties. Extractors provide a way to
obtain almost uniformly distributed random bits from weak random
sources using only a small random seed as a catalyst.

These objects have found numerous applications in computer science and
serve as important tools in both algorithmic and complexity-theoretic
settings. Despite the disparate definitions of codes, expanders and
extractors, several recent results have established fascinating
interconnections between these objects, and in particular used one to
construct and shed insight on others. This course will discuss
constructions of error-correcting codes, expander graphs, and
extractors with emphasis on these recent developments, and will draw
its material from a collection of recent research papers.

Even the study of any *one* of these objects in considerable depth
cannot be fit in a quarter. Therefore, this course will be no where
close to a comprehensive introduction to all facets of any one of
these areas. In particular this is NOT a "conventional" course in
coding theory.  However, while exploring the interconnections, we will
see some very good, and sometimes near-optimal, constructions of these
objects.

-------------------------------------------------------

ASSUMED BACKGROUND: The course will sketch the necessary background
from coding theory and give pointers where proofs or further details
can be found about results that we borrow from the literature.
Likewise for some basic results concerning expanders and extractors.
Taking a few of these basic theorems on faith, the rest of the course
should not need any specific background other than "mathematical
maturity", or less vaguely, comfort with basic probability theory,
combinatorics, and algebra.

-------------------------------------------------------