General Information | Motivation | Prerequisites | Readings | Homework | Topics | Class Requirements | Projects | Lecture Notes and Readings | Academic Honesty Policy
Instructor: Rocco Servedio (517 CSB, office hours by appointment.)
Email: rocco at cs dot columbia dot edu.
TA: TBA
Room: 606 MLK
Time: Wed 2:10-4:00 pm
This is a three-credit advanced graduate level course on the analysis of Boolean functions. The course can be used as a theory elective for the Ph.D. program in computer science, as a track elective course for MS students in the "Foundations of Computer Science" track, or as a track elective for undergraduates in the "Foundations" track. Auditing the class requires the approval of the instructor.
If you are an undergraduate student in SEAS, Columbia College, General Studies or Barnard who would like to register for this class, please contact me with a brief description of your background in CS theory and mathematics courses.
This course will focus on analytic approaches to understanding Boolean functions, by studying their Fourier representations. The plan is to study
Students will do a few homework exercises and turn in their annotations of lecture notes (more on this below) and work on a final project which will have a written component and an in-class presentation component. The final project is an opportunity to work on original research in the analysis of Boolean functions.
The course will not include any programming.
Each student/team will also have a separate role as an SAS (Supportive Audience Simulator) for another team. In this role, you will serve as a simulated audience member for a "dry run" of the project presentation that the other student/team will carry out. Your job in this role is to provide helpful and constructive feedback so that the other student/team can give the best possible presentation. This written feedback (a paragraph or two) should be sent both to the other student/team and to the instructor via email.
Topic selection: The projects page lists many possible topics; you are also encouraged to come up with your own topic (subject to instructor approval). Many potential project topics will be proposed during the course of our lectures.
Progress report: About a month before the final project due date you will turn in a progress report describing what you've done and outlining goals for your presentation; see the projects page for details.
Presentation: The goal of your presentation should be to give a comprehensible explanation of an important result in your topic (this is the goal for the instructor in his lectures on the topics he covers as well). Presentations will take place towards the end of the semester. The length of each presentation will be determined based in part on the number of students in the class.
Final report: The final report will have two components.
(1) Background: explain the topic and give a clear and thorough exposition of prior work on this topic. This should include at the very least a detailed set of lecture notes for the material covered in your presentation, similar to the notes that the instructor distributes for the various units throughout the semester. Since the presentations are not likely to be extremely long, this background section should likely cover additional material not in your presentation as well.
(2) Research: Identify an interesting and worthwhile research question in this area and describe why the question is interesting and your work on this question. Students are encouraged to spend significant effort on the research component; ideally, this portion of the project will lead to a new publishable research result in the topic you pursue, but this is not necessary in order to do a successful project.
You will turn in an initial proposal fairly early in the semester (basically just to identify the topic for your project).
See the projects page for a detailed schedule of what needs to be turned in by when.
A breakdown: ``Readings'' are written sources for results we covered/proved in class (and they often contain a lot of other material that we didn't cover in class as well). ``Supplemental readings'' are written sources for results that we talked about but possibly/likely without proofs in class --- these are good starting points if you're interested in a possible project on those topics.
Clean lecture notes Annotated lecture notes
Readings: O'Donnell textbook 1.1-1.4. The DT versus CDNF result is from this paper of Jukna, Razborov, Savicky and Wegener.
Clean lecture notes Annotated lecture notes
Readings: O'Donnell textbook 2.2-2.3, and just a smidgen of 11.1 for Gaussian stuff. The log(n) - O(log log n) lower bound on degree for a Boolean function depending on all n variables is from this paper of Nisan and Szegedy.
(Back to the Boolean setting) Noise: Noise sensitivity, noise stability, and the noise operator for Boolean functions.
See above for clean lecture notes for the unit on influences and noise. Annotated lecture notes for the rest of the influence and noise unit
Readings: O'Donnell textbook 2.4 and a bit of 11.2.
Supplemental readings: The influence notion for symmetric convex sets that we mentioned is from this paper. Talagrand's Boolean correlation inequality is proved here and the analogous quantitative correlation bound for the Gaussian setting is from this paper.
Clean lecture notes. Annotated lecture notes.
Polynomial threshold functions (PTFs). PTF degree. The Gotsman-Linial conjecture. Gaussian noise sensitivity, Gaussian noise stability, Gaussian noise operator. Start upper bound on Gaussian noise sensitivity of PTFs.
See above for clean lecture notes for the unit on LTFs. Clean lecture note on PTFs. Annotated lecture notes for the rest of the LTF unit. Annotated lecture notes on PTFs.
Finish upper bound on Gaussian noise sensitivity of PTFs.
Return to LTFs: Upper bound on average sensitivity of intersections of halfspaces.
Start decision trees: Basics. Every decision tree has an influential variable: discussion.
See above for clean lecture notes for the unit on PTFs. Annotated lecture notes for the rest of the PTF unit. Clean lecture notes on DTs. Annotated lecture notes on what we covered of the DT unit.
Continue decision trees: Every decision tree has an influential variable: inductive proof of the two-function version. Total influence of decision trees: Every size-s decision tree has total influence at most log(s). A sharpening for monotone functions: every monotone function computed by a size-s decision tree has total influence at most sqrt{log(s)}. A proof based on analyzing subcubes. A proof based on ``erase-all-subscripts'' symmetrization.
See above for clean lecture notes for the DT unit. Annotated lecture notes on DTs.
Depth-2 circuits: DNF and CNF formulas. DNFs for the parity function: computing and approximating (upper and lower bounds). DNFs for Majority: computing and approximating (upper and lower bounds).
Clean lecture notes on depth-2 circuits. Annotated lecture notes on depth-2 circuits.
Depth-2 circuits concluded: inability of DNFs to approximate CNFs (via random projection arguments). Learning Boolean functions using random examples. Estimating Fourier coefficients. Learning by Fourier approximation: the "low-degree algorithm". Applications of Fourier concentration: learning monotone functions, halfspaces, intersections of halfspaces, and DNFs. Doing better via Switching Lemma based analysis.
Clean lecture notes on learning. Annotated notes on learning.
Learning Boolean functions using random examples continued: Taking advantage of monotonicity (modified low-degree algorithm): learning monotone DNF and monotone decision trees. Learning Boolean functions using membership queries: finding large Fourier coefficients. Application: learning decision trees and sparse polynomials. Start discussion of hypercontractivity and KKL theorem.
Annotated notes on learning. Annotated lecture notes on hypercontractivity and KKL (initial).
Motivation for KKL theorem: Boolean functions as voting rules. Reasonable random variables. Bonami's Lemma. (2,4)-hypercontractivity and noise sensitivity of small sets. The KKL Theorem. Friedgut's Theorem.
Fully annotated lecture notes on hypercontractivity and KKL (initial).
AI Policy. It's 2026, and for better or worse AI is out there. AI is very good at producing artifacts which, in the past, were evidence of human understanding. In this brave new world it is now possible to generate those artifacts without human understanding. The goal of this course is to foster human understanding (of the analysis of Boolean functions). AI can be a great tool to help with this goal, but it can also get in the way.
Less abstractly: you are permitted to use AI to help you understand course material --- you can ask it any question you like. But you are advised to use AI in a thoughtful way which will promote your thinking and growth rather than substituting for it --- you won't learn much by just having AI solve a problem or write a report for you. Used well, AI can be a great tool that can help you figure out how to understand results, solve problems, and explain ideas (all of which are essential parts of the research process) yourself. Henry Yuen's AI policy for his quantum computing course, which you can find here, has good examples and suggestions of how to use AI in a smart way to help develop your own understanding.
Even less abstractly, there are three important caveats about how you are permitted to use AI in this course:
(1) all written work you turn in needs to be handwritten or hand-typed with your own human fingers and using your own human words. You can read and understand an AI-generated response to a question, but you need to write your own solution to help promote your own understanding.
(2) You need to turn in a transcript of your interactions with AI whenever it is part of the process by which you generate any written work for this class. You will not be penalized in any way for using AI; the reason for this is to help you use AI in a productive way which promotes your own growth and augments your understanding, rather than in a "just tell me the answer" kind of way.
(3) You are strongly encouraged to grapple with challenging material on your own and try to figure things out for yourself before consulting AI since this is an essential part of your own intellectual growth and of learning how to think about problems as a reseacher. As a wise person once said, you are encouraged to use your own best judgement about what will best help your learning when using AI.