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!
The purpose of the course project is to enable a more in-depth study of a question related to the analysis of Boolean functions.
This project can take many different forms, but the most straightforward way to approach it is to identify a state-of-the-art result that you find particularly interesting and then work on understanding it very well: its context (i.e., why the result is interesting; what was known before it), its proof, and what is an interesting open problem that is suggested but not covered by the result. You should then try to solve that open problem and describe what you tried (and what partial—or complete!—results you obtained), but new results are not required for the final project to be successful.
There are three deliverables for the project:
The presentation will be a short 10 minute overview of your project. The goal of your presentation is to describe the topic of your project to the rest of the class and, most importantly, why it might be interesting for them. Given the short time we have for the talks, you are encouraged to make (a very small number of) slides for your talk, though you are free to use the board instead if you prefer to do so.
The final project report should be typeset in LaTeX and presented in the format of a research article. I.e., with an introduction that describes the topic you studied and presents the context (high-level motivation, related results, etc.) for this topic, followed by more technical sections where (i) you provide a complete proof of the main result you studied (in your own words), and (ii) describe the approaches and partial results obtained on the open problem you tackled. There is no upper or lower limit on the length of the final project report, around 10 pages (say, 6-14 pages) should be both necessary and sufficient for almost everyone.