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.
||Coding theory Rate and distance, Reed-Solomon and BCH codes, bounded independence.||[pdf]|
||The Gilbert-Varshamov bound, concatenation, small-bias sets.||[pdf]|
||No class, Year of the Dragon|
||Decoding and list-decoding. Secret sharing from codes.||[pdf]|
||Local decoding. Reed-Muller codes. Relations between worst-case and average-case hardness.||[pdf]|
||Analysis of boolean functions Fourier decomposition. The Kushilevitz-Mansour algorithm.||[pdf]|
||The Fourier spectrum of shallow circuits.||[pdf]|
||Gowers uniformity and low-degree testing.||[pdf]|
||Fourier analysis, small-biased sets, and pseudorandomness.||[pdf]|
||Hardness of approximation for some constraint satisfaction problems.||[pdf]|
||Expanders Eigenvalues, random walks, and an application to hardness of approximation.||[pdf]|
||No class, Ching Ming Festival|
||Cayley graphs and Kazhdan constants. The Margulis-Gabber-Galil expander.||[pdf]|
||Two applications of expanders to small-biased sets.||[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: