Codes, Boolean Functions, and Expanders

Special Lectures on Mathematical and Information Sciences IV
Tokyo Institute of Technology, Fall 2013

Recent Announcements

Course Description

The objects we will study in this class — error-correcting codes, Boolean functions, and expander graphs — have turned out to be extremely useful in various areas of theory of computing. We will see them making unexpected appearances to shed light on problems in learning theory, cryptography, computational complexity, pseudorandomness, and hardness of approximation.

Although the material is diverse, the lectures will be self-contained. You do not need any background beyond discrete probability and basic algebra. We start every lecture with a motivating problem, discover how it relates to the object under study, and develop just enough mathematics for a solution.

This course was designed with the beginning graduate student in mind. The examples are meant to illustrate how one goes about formulating and tackling research problems in the theory of computing.


This is a tentative plan for the topics to be covered this semester. Changes are possible and you are welcome to suggest other things you would like to see in the class.

date topic notes
1Oct 11
Codes Rate and distance. Two-source hitters. [pdf]
2Oct 18
Reed-Solomon codes, bounded independence, the Plotkin bound. [pdf]
3Oct 25
The Gilbert-Varshamov bound, concatenation, small-biased sets.
4Nov 1
Decoding and list-decoding. Secret sharing. [pdf]
5Nov 8
Boolean functions Fourier decomposition. The linearity test. [pdf]
6Nov 15
Learning heavy Fourier coefficients. The Goldreich-Levin theorem. [pdf]
7Nov 22
Fourier analysis of the long code. [pdf]
8Nov 28
Hardness of MAX-3LIN.
9Dec 5
Expanders Introduction. [pdf]
10Dec 13
Eigenvalues, random walks, edge expansion.
11Dec 20
Cayley graphs and small-biased sets. Raghavendra's algorithm for linear equations mod 2. [pdf]


Course Information


Notes will be provided for every lecture. There is no required textbook. Links to other material may also be provided for some lectures. The following materials may give you an idea about some of the topics: