Tokyo Institute of Technology, Fall 2013

**Lectures**Fri 15:05-16:30 in W832**Instructor**Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, office W1107**Office hours**Fri 11:00-12:00

**Dec 13**You are invited to an end-of-class party on Fri Dec 20 at 6.30pm.**Dec 13**Homework 3 is posted. It is due on Fri Dec 27. Please send the solutions over email.

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

1 | Oct 11 |
Codes Rate and distance. Two-source hitters. |
[pdf] |

2 | Oct 18 |
Reed-Solomon codes, bounded independence, the Plotkin bound. | [pdf] |

3 | Oct 25 |
The Gilbert-Varshamov bound, concatenation, small-biased sets. | |

4 | Nov 1 |
Decoding and list-decoding. Secret sharing. | [pdf] |

5 | Nov 8 |
Boolean functions Fourier decomposition. The linearity test. |
[pdf] |

6 | Nov 15 |
Learning heavy Fourier coefficients. The Goldreich-Levin theorem. | [pdf] |

7 | Nov 22 |
Fourier analysis of the long code. | [pdf] |

8 | Nov 28 |
Hardness of MAX-3LIN. | |

9 | Dec 5 |
Expanders Introduction. |
[pdf] |

10 | Dec 13 |
Eigenvalues, random walks, edge expansion. | |

11 | Dec 20 |
Cayley graphs and small-biased sets. Raghavendra's algorithm for linear equations mod 2. | [pdf] |

**Prerequisites**There are no formal prerequisites for this class, but it helps to be comfortable with discrete mathematics and probability.**Grading and homeworks**Your grade will be determined from homeworks (30%), a take-home midterm exam (30%), and a final project (40%). Two to three homeworks, each containing 4-5 problems, will be issued throughout the semester. You are encouraged to collaborate on them as long as you write up your own solutions. The take-home exam will be of a similar format as the homeworks, but you will work on it independently.**Final project**For your final project you will be expected to do some independent reading, a presentation in class, and a short report. Some suggestions for projects and more details will be provided around the middle of the semester.

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:

- Venkat Guruswami: Introduction to coding theory.
- Ryan O'Donnell: Analysis of boolean functions.
- Shlomo Hoory, Nati Linian, Avi Wigderson: Expander graphs and their applications [pdf].