COMS 6298: Boolean Function Analysis, Fall 2026

COMS 6298: Boolean Function Analysis
Fall 2026

General Information

Instructor: Rocco Servedio (517 CSB, office hours by appointment.) Email: rocco at cs dot columbia dot edu.
TA: TBA
Room: TBA
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.

Motivation

Boolean functions, i.e. functions which map strings of 0s and 1s to 0/1-valued outputs, are among the most basic objects of study in theoretical computer science and mathematics. Results about Boolean functions arise across many subfields of theoretical computer science research such as complexity theory, learning theory, cryptography, sublinear algorithms and property testing, hardness of approximation, and more. Ideas and ingredients from the study of Boolean functions also pop up, sometimes unexpectedly, in other areas of math such as high-dimensional geometry and probability, combinatorics, statistical physics, and beyond.

This course will focus on analytic approaches to understanding Boolean functions, by studying their Fourier representations. The plan is to study

basic properties and crucial analytic parameters of Boolean functions (influence, noise sensitivity, Fourier concentration, etc);

analytic properties of important types of Boolean functions (decision trees, linear threshold functions, logical circuits such as DNF formulas, monotone functions, etc);

connections to Gaussian space;

hypercontractivity and the theorems of Kahn, Kalai and Linial and Friedgut;

central limit theorems and the invariance principle; and

applications of the various results we establish to problems in different areas such as computational learning theory.

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.

Prerequisites

The most important prerequisite is "mathematical maturity"; you should be comfortable with proofs, basic discrete math, combinatorics, probability, and linear algebra. Among other things, you should be completely comfortable with the probability basics covered in this brief note, and you should be comfortable with using the tail bounds covered in this brief overview of standard tail bounds. In general, a solid undergraduate-level mathematics background is good preparation. If you have questions about your mathematical readiness you should contact the instructor before enrolling.

The course will not include any programming.

Readings

There is no single source for the material we will cover, but the book by Ryan O'Donnell on analysis of Boolean functions (see the top right part of his web page, linked above) is a comprehensive resource for many of the topics that we'll cover (and many that we will not cover). Links to specific readings for each lecture will be posted as the semester progresses.

Homework

Here is a list of the official homework problems (this list will be updated as the semester progresses). You need to turn in one HW problem by October 9, one HW problem by November 9, and one HW problem by December 9 (though it's not a bad idea to turn in all three required homework problems earlier in the semester). All HW problems should be turned in by email directly to the instructor.

List of Topics

This is a rough list of anticipated topics which is subject to change and revision. We may skip some of these or cover additional topics as determined by time and the interest/background of the couse participants.

The basics: Functions on the Boolean hypercube: examples. Parity functions and Fourier representations. Parseval and Plancherel. "Fourier concentration". Examples of important types of functions. Application: Decision tree size versus CDNF size.
Influence and noise: Coordinate influences and total influence. Sensitivity. Examples. Fourier interpretations. Derivatives. Poincare's inequality. Application: degree of Boolean functions. Influence and Fourier concentration. Examples: DNF formulas, monotone Boolean functions. Convex sets and monotone Boolean functions. Basics of Hermite analysis. The "Boolean-Gaussian Analogy". Monotone functions, influences, and correlations. Harris-Kleitman and the Gaussian Correlation Theorem. Quantitative correlation inequalities. Noise: noise sensitivity, noise stability, correlated inputs, the noise operator. Fourier interpretations and relation to Fourier concentration.
Special Functions I: Halfspaces (aka LTFs). Noise sensitivity of LTFs and functions of LTFs. "Chow Parameters" of LTFs: the Gotsman-Linial Theorem, Khintchine's inequality. Level-1 weight of general Boolean functions. Chow's Theorem for LTFs. Polynomial threshold functions (PTFs). PTF degree. The Gotsman-Linial conjecture. Gaussian noise sensitivity, Gaussian noise stability, Gaussian noise operator. Gaussian noise sensitivity of PTFs. Total influence and noise sensitivity of intersections of halfspaces.
Special Functions II: Decision Trees: Every decision tree has an influential variable: inductive proof, and proof by pruning. Total influence of decision trees. Total influence of monotone decision trees. Symmetrization-based proof.
Special Functions III: Depth-Two Circuits: DNFs for the parity function: computing and approximating (upper and lower bounds). DNFs for Majority: computing and approximating (upper and lower bounds). Inability of DNFs to approximate CNFs (via random projection arguments). Every decision tree has an influential variable: inductive proof, and proof by pruning. Total influence of decision trees. Total influence of monotone decision trees. Symmetrization-based proof.
Learning Boolean Functions I: 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. Taking advantage of monotonicity (modified low-degree algorithm): learning monotone DNF and monotone decision trees.
Learning Boolean Functions II: Membership Queries: Finding large Fourier coefficients. Application: learning decision trees and sparse polynomials.
Hypercontractivity: Reasonable random variables. Bonami's Lemma. (2,4)-hypercontractivity and noise sensitivity of small sets. The KKL Theorem. Friedgut's Theorem. (2,q)-hypercontractivity. Applications: "degree-d Chernoff bounds", small-set expansion.
Central Limit Theorems and Invariance: Kolmogorov distance. The Berry-Esseen Theorem. Test functions and mollifiers. Invariance for sums of random variables. The Invariance Principle for low-degree polynomials.

Class Requirements

The requirements of the course are as follows:

Attendance and class participation (15% of grade) Students are expected to come to lecture and are encouraged to to participate. Lectures are meant to be highly interactive sessions during which the instructor and the students talk through the material in the lecture notes together.
Sporadic homework (15% of grade): Occasionally in lecture I will state a result in class without proof and designate its proof as an "official homework problem." You don't need to do every homework problem, but you must complete and turn in three homework problems over the course of the semester: one by Oct 9, one by Nov 9, one by Dec 9 (though you may find it easier to just get the homework out of the way early in the semester) . Here is a list of the official homework problems (this list will be updated as the semester progresses).
Lecture Note Annotations (20% of grade): I will distribute detailed lecture notes, and during lectures we will go over these notes together. Each student will need to turn in a copy of the lecture notes for one unit (other than Unit Zero) on which you have made detailed handwritten annotations demonstrating your own engagement with the material. This needs to be turned in by the start of the Thanksgiving break (by email directly to the instructor).
Final project (50% of grade): Each student will select a topic for a final project; study that topic; write a preliminary progress report; write a final project report; and give a presentation. The last few lectures will be devoted to student presentations. You are allowed to work in teams (exact limits on team sizes TBD).
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.

The plan is to grade the class very generously; what you get out of the class will be proportional to what you invest in the class. The goal is for the class to be a relaxed, fun, interactive exploration of the wonders of Boolean function analysis both for the instructor and for the students.

Lecture Notes

The detailed notes for each lecture will be posted here after the lecture, along with lecture-relevant readings.

Lecture 1: (9/09/2026)

Lecture 2: (9/16/2026)

Lecture 3: (9/23/2026)

Lecture 4: (9/30/2026)

Lecture 5: (10/7/2026)

Lecture 6: (10/14/2026)

Lecture 7: (10/21/2026)

Lecture 8: (10/28/2026)

Lecture 9: (11/4/2026)

Lecture 10: (11/11/2026)

Lecture 11: (11/18/2026)

Lecture 12: (12/03/2026)

Lecture 13: (12/10/2026)

Academic Honesty Policy

By taking the course, students are presumed to consent to the Computer Science departmental policy on academic honesty. This policy has been passed by the faculty of the Department and approved by the school deans. The policy will be enforced for all courses, including this one. You can find the text of the policy at http://www.cs.columbia.edu/education/honesty. For this course in particular, students should be sure to provide appropriate citations for all sources used in their project reports.

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.