CS 6817: Analysis of Boolean Functions (Spring 2025)
Instructor: Eshan Chattopadhyay
Class schedule: TR 10:10-11:25am
Location: Phillips Hall 213 map
Office hour: M 2:15-3:15 pm, or by appointment.
Logistics:
We will use Ed for announcements/discussions and Canvas for HW posting and submission.
About this course: A central focus of this course will be to uncover properties of Boolean functions via analytic methods (such as studying their Fourier spectrum). Such methods have seen remarkable applications in various fields of theoretical computer science such as property testing, hardness of approximation, learning theory, pseudorandomness, etc, and is by now an essential ingredient in a theorist's toolkit. These methods have also found nice applications beyond computer science, in areas such as combinatorics, random graphs and metric spaces. We will develop this theory from the basics and cover a variety of applications in the course.
Prerequisites: CS 4820 or permission from the instructor. In general, some mathematical maturity is expected. Familiarity with basic notions of algebra (such as finite fields, basics of vector spaces, polynomials), linear algebra, discrete probability, and basics of computational complexity theory will come in handy.
Grading: Performance in this course will be evaluated as follows:
- Homeworks: 40%. There will be 4 homework assignments well spread in the semester. Solving problems will require original thinking, and it will be a good idea to start early. You will be required to use LaTeX to typeset your solutions.
- Project: 40%. You are expected to pick a topic and send a project proposal by March 25 (Tuesday). You may work in groups (up to 3 members).
- Scribe notes: 15%. You are expected to scribe 1 or 2 lectures (depending on enrollment). You will be required to submit an initial draft of the scribed notes within 48 hours after the lecture.
Here is template
that you can use.
- Participation: 5%.
Resources
The main reference for the course will be scribed lecture notes. We will closely follow the excellent book Analysis of Boolean Functions by Ryan O'Donnell. You can buy the book or find a draft of the book here .
The following are some very useful resources:
- Fantastic lecture notes by Hamed Hatami.
- Some open problems to think about during the course!
- See this amazing list of resources compiled by Li-Yang Tan.
(will be updated as the semester progresses)
- Lecture 1: Introduction, existence and uniqueness of Fourier expansion. notes
- Lecture 2: Basic Fourier analystic formulas, introduction to linearity testing. notes
- Lecture 3: BLR Linearity Test. notes
- Lecture 4: Introduction to influence of variables. notes
- Lecture 5: Fourier formulas for influence, Poincaré inequality. notes
- Lecture 6: Monotone functions, Noise Stability. notes
- Lecture 7: More on Noise Stability, Condorcet elections. notes
- Lecture 8: Arrow's Theorem, basics of Fourier concentration. notes
- Lecture 9: Fourier concentration of decision trees, application to PAC learning. notes
- Lecture 10: Low-degree algorithm, Kushilevitz-Mansour algorithm. notes
- Lecture 11: Goldreich-Levin algorithm notes
- Lecture 12: DNFs: Fourier Concentration via influence notes
- Lecture 13: Random Restrictions and Fourier Analysis notes
- Lecture 14: Better concentration of DNFs via Random restrictions notes
- Lecture 15: Hypercontractivity and Small-Set Expansion of the Noisy Hypercube notes
Inclusiveness
You should expect and demand to be treated by your classmates and the course staff with respect.
You belong here, and we are here to help you learn and enjoy this course.
If any incident occurs that challenges this commitment to a supportive and inclusive environment, please let the instructors know so that the issue can be addressed.
We are personally committed to this, and subscribe to the
Computer Science Department's Values of Inclusion.