Codes, Boolean Functions, and Expanders

Special Lectures on Mathematical and Information Sciences IV
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

Recent Announcements

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

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.

Lectures

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]

Homeworks

• Homework 3 due Fri Dec 27
• Homework 2 due Fri Nov 22
• Homework 1 due Fri Nov 1

Course Information

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

References

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