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.
||Codes Rate and distance. Two-source hitters.||[pdf]|
||Reed-Solomon codes, bounded independence, the Plotkin bound.||[pdf]|
||The Gilbert-Varshamov bound, concatenation, small-biased sets.|
||Decoding and list-decoding. Secret sharing.||[pdf]|
||Boolean functions Fourier decomposition. The linearity test.||[pdf]|
||Learning heavy Fourier coefficients. The Goldreich-Levin theorem.||[pdf]|
||Fourier analysis of the long code.||[pdf]|
||Hardness of MAX-3LIN.|
||Eigenvalues, random walks, edge expansion.|
||Cayley graphs and small-biased sets. Raghavendra's algorithm for linear equations mod 2.||[pdf]|
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: