Many of the most fundamental questions in computer science are in fact questions about an elegant combinatorial object: the Boolean function. In this course, we will see how tools from Fourier analysis can be used to answer some of these questions, covering results in such varied areas as learning theory, sublinear-time algorithms, and circuit complexity.
The most important requirement for the class is mathematical maturity, along with a solid understanding of combinatorics, probability theory, and the analysis of algorithms. No previous background in Fourier analysis will be required for the class.
The model of the class is a guided independent study of the topic. The weekly lectures will aim to be supplementary to the independent reading of the textbook by the students, with a focus on clarifying and expanding on the material from the book.
There will be 5 assignments containing selected exercises from the class textbook throughout the term. The students will also get to explore one of the topics covered in the course in more depth via a class project.
The textbook for the class is Analysis of Boolean Functions by Ryan O'Donnell. We will follow the textbook closely throughout the term, so the best way to see if the material is of interest to you is to read the first chapters of the book.
The assignments will be added here as they become available.
Amit will also be regularly adding bonus problem sets below. Enjoy!
More information on the class project will be added here.