Topics in (and out) the theory of computing

The Chinese University of Hong Kong, Spring 2012

Recent Announcements

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.


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

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: