Topics in (and out) the theory of computing

The Chinese University of Hong Kong, Spring 2012

• Lectures Wed 11:30-2:15 in ERB 804
• Instructor Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926
• Office hours Fri 10.30-12.30 (or by appointment)

Recent Announcements

• Apr 23 The presentation on Wednesday will be in the usual classroom (ERB 804). Please try to finish your presentation in 15 minutes.
• Apr 16 In problem 1 of homework 3 assume that f is balanced (E[f(x)] = 1/2), otherwise part (b) is not true. I also fixed an issue in problem 3.
• Apr 11 Homework 3 is due on Wed Apr 25 in class.

Course Description

This course will cover tools and techniques that have proven useful in the theory of computing over the years. They have contributed to advances in many areas inside and outside theory, like learning, cryptography, and optimization. These techniques often originate from distant fields like algebra, signals, and information theory. They found their way into computer science through the effort of passionate graduate students like you, who dazzled the world by mastering them applying them towards solving hitherto intractable problems. It is time for you to continue this tradition!

Regardless of your area of expertise (it doesn't have to be theory), try this course, become more confident in your technical skills, go forth, and make a splash.

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	reading
1	Jan 11	Coding theory Rate and distance, Reed-Solomon and BCH codes, bounded independence.	[pdf]
2	Jan 18	The Gilbert-Varshamov bound, concatenation, small-bias sets.	[pdf]
	Jan 25	No class, Year of the Dragon
3	Feb 1	Decoding and list-decoding. Secret sharing from codes.	[pdf]
4	Feb 8	Local decoding. Reed-Muller codes. Relations between worst-case and average-case hardness.	[pdf]
5	Feb 15	Analysis of boolean functions Fourier decomposition. The Kushilevitz-Mansour algorithm.	[pdf]
6	Feb 22	The Fourier spectrum of shallow circuits.	[pdf]
7	Feb 29	Gowers uniformity and low-degree testing.	[pdf]
8	Mar 7	Fourier analysis, small-biased sets, and pseudorandomness.	[pdf]
9	Mar 14	Hardness of approximation for some constraint satisfaction problems.	[pdf]
	Mar 21	No class
10	Mar 28	Expanders Eigenvalues, random walks, and an application to hardness of approximation.	[pdf]
	Apr 4	No class, Ching Ming Festival
11	Apr 11	Cayley graphs and Kazhdan constants. The Margulis-Gabber-Galil expander.	[pdf]
12	Apr 18	Two applications of expanders to small-biased sets.	[pdf]
	Apr 25	Project presentations

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%). Three homeworks will be issued throughout the semester. You are encouraged to collaborate on the homeworks as long as you write up your own solutions.
• Final project For your final project you will be expected to do some independent reading, a presentation in class, and a short report. A list of suggested 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].