Source-linked AI summary
Analysis of Boolean Functions
Ryan O'Donnell
TL;DR
The text studies Boolean functions through analytic tools including Fourier expansions and Gaussian invariance. It develops applications spanning learning, testing, computational complexity, and Gaussian geometry, while identifying open problems and technical scope boundaries.
Problem
Boolean-function analysis addresses questions about learning, testing, noise stability, Gaussian approximation, and the efficiency or hardness of combinatorial problems.
Method
The approach uses Fourier analysis, invariance principles, Gaussian reductions, and complexity-theoretic reductions to study Boolean-function properties and applications.
Results
The text presents results including Gaussian approximation for low-degree or uniformly noise-stable functions with small influences, exact learnability of degree-k functions, a 6-query dictator tester, and hardness reductions for Max-E3-Sat.
Takeaways & Limitations
Boolean-function analysis connects structural properties such as influence and noise stability to results in Gaussian geometry, learning theory, property testing, and computational complexity.
Takeaways & Limitations
Whether majority is extremal for the stated theorem remains an open problem, and some stated definitions require minor technical amendments.
Abstract
from arXiv · showhide
The subject of this textbook is the analysis of Boolean functions. Roughly speaking, this refers to studying Boolean functions $f : \{0,1\}^n \to \{0,1\}$ via their Fourier expansion and other analytic means. Boolean functions are perhaps the most basic object of study in theoretical computer science, and Fourier analysis has become an indispensable tool in the field. The topic has also played a key role in several other areas of mathematics, from combinatorics, random graph theory, and statistical physics, to Gaussian geometry, metric/Banach spaces, and social choice theory. The intent of this book is both to develop the foundations of the field and to give a wide (though far from exhaustive) overview of its applications. Each chapter ends with a "highlight" showing the power of analysis of Boolean functions in different subject areas: property testing, social choice, cryptography, circuit complexity, learning theory, pseudorandomness, hardness of approximation, concrete complexity, and random graph theory. The book can be used as a reference for working researchers or as the basis of a one-semester graduate-level course. The author has twice taught such a course at Carnegie Mellon University, attended mainly by graduate students in computer science and mathematics but also by advanced undergraduates, postdocs, and researchers in adjacent fields. In both years most of Chapters 1-5 and 7 were covered, along with parts of Chapters 6, 8, 9, and 11, and some additional material on additive combinatorics. Nearly 500 exercises are provided at the ends of the book's chapters.
Prefaces
This revised textbook develops the foundations of Boolean-function analysis while surveying applications across theoretical computer science and mathematics. It is designed both as a research reference and as a graduate-course text.
- Revision: The May 2021 revision fixes more than 100 small typos and errors without adding essentially new mathematical content.The book remains a snapshot of the field around 2014.
- Scope: The book studies Boolean functions through Fourier expansion and other analytic means, a subject central to theoretical computer science and several mathematical areas.Applications include combinatorics, random graph theory, statistical physics, Gaussian geometry, metric/Banach spaces, and social choice theory.
- Applications: Each chapter ends with a highlight illustrating applications in areas including property testing, cryptography, learning theory, pseudorandomness, and hardness of approximation.The overview is explicitly broad but not exhaustive.
- Use: The text can serve as a working-researcher reference or the basis of a one-semester graduate course, with nearly 500 exercises.The author reports teaching such a course at Carnegie Mellon University to students and researchers from computer science, mathematics, and adjacent fields.
Boolean functions and the Fourier expansion
The chapter develops Fourier analysis of Boolean functions and connects spectral structure to influences, noise, voting, learning, and circuit representations. Its results include structural theorems, testing and learning guarantees, and transformations between computational models.
- Fourier foundations: Fourier convolution multiplies pointwise in the spectrum, and the BLR test’s acceptance implies closeness to a linear character.For sufficiently small error, the closeness improves to approximately ϵ/3, and this is sharp.
- Influence: Total influence ranges from 0 for constants to n for parity, while transitive-symmetric monotone functions have each coordinate influence at most 1/√n.The Poincaré inequality connects influence with Fourier weight above degree zero.
- Learning: Fourier concentration supports learning: degree-k Boolean functions are exactly learnable from random examples in time n^k · poly(n,2^k), and query learning follows from concentration on few sets.Related guarantees cover bounded influence, monotone functions, noise-stable classes, decision-tree size, and bounded Fourier 1-norm.
- Representations: Decision trees of size s and depth k convert to DNFs and CNFs of size at most s and width at most k, while DNF width w implies total influence at most 2w.These representation bounds connect computational structure with analytic quantities.
Generalized domains
The chapter develops Fourier analysis beyond the Boolean cube, showing that product-space Fourier bases support basis-independent formulas and connect analytic quantities to threshold, influence, and hypercontractive results.
- Fourier bases: A Fourier basis is an orthonormal basis containing the constant function 1, and tensor products of its elements form a Fourier basis for product spaces.The all-zero multi-index represents the constant function.
- Basis independence: The resulting Fourier formulas for functions on product spaces do not depend on which product Fourier basis is chosen.The text notes that a basis-independent formulation is developed subsequently.
- Thresholds and influence: For monotone Boolean functions, sharp thresholds correspond roughly to superconstant total influence under the critical probability distribution.For majority, the threshold around p = 1/2 sharpens with n because the derivative there equals total influence Θ(√n).
- Threshold bounds: OSSS-based bounds apply to monotone transitive-symmetric functions and can lower-bound threshold width; the bound is strongest for critical probability Θ(1/n) or 1−Θ(1/n).For critical probability 1/2, an infinite family attains threshold width O(n^2/3 log n), up to a logarithmic factor relative to the general bound.
hypercontractivity
The chapter completes hypercontractivity for uniform ±1 bits and extends (p,2) and (2,q) results to arbitrary product probability spaces. These extensions support consequences including small-set expansion, influence bounds, junta structure, sharp thresholds, and low-degree projection control.
- Generalization: The generalized hypercontractivity theorem gives ∥Tρ f∥q ≤ ∥f∥2 and ∥Tρ f∥2 ≤ ∥f∥q′ on arbitrary product probability spaces.The result follows from one-dimensional inequalities through hypercontractivity induction.
- Generalization: Randomization and symmetrization can remove dependence on the minimum atom probability λ, including in Bourgain’s Sharp Threshold Theorem.Without this technique, consequences may have quantitatively worse parameters depending on λ.
- Random variables: For mean-zero random variables, the largest admissible hypercontractive ρ is within a q-dependent constant of ∥X∥2/∥X∥q.The chapter also gives sharp or optimal bounds for symmetric and discrete variables.
- Applications: The general theory yields KKL- and Friedgut-type structural results for Boolean functions on product spaces.These include lower bounds on maximum influence and approximation by juntas whose size depends on λ, total influence, and error.
- Applications: Hypercontractivity also supports sharp-threshold results and generalizations of the Majority Is Stablest theorem.The chapter connects these results to monotone transitive-symmetric functions and product-space domains.
- Applications: Low-degree projection increases q-norms by at most a factor Cq depending only on q.The chapter states ∥f≤k∥q ≤ Cq^k∥f∥q, with C4,C4/3 = 5 as available constants.
2 Borell Isoperimetric Theorem. Fix θ ∈(0, π
The chapter develops Gaussian isoperimetry and invariance principles connecting Boolean functions, Gaussian geometry, and approximation results. It shows that low-degree, small-influence functions behave similarly under discrete and Gaussian inputs and applies this framework to Max-Cut hardness.
- Gaussian geometry: Gaussian Isoperimetric Inequality states that among sets of fixed Gaussian volume, halfspaces have minimum Gaussian surface area.For a halfspace of volume α, the surface area is U(α).
- Gaussian geometry: The Gaussian surface area of intersections of k halfspaces is at most O(√log k), while degree-k polynomial threshold sets satisfy a bound depending on k.The intersection bound is tight for appropriately sized cubes in R^k.
- Invariance principles: The invariance principle compares expectations of smooth test functions for independent random variables with matching first and second moments.The comparison error is controlled by the test function’s third derivative and a sum of third-moment terms.
- Invariance principles: Low-degree, small-influence Boolean functions have distributions close under discrete and Gaussian inputs for Lipschitz tests and in Lévy distance.The stated Lévy bounds include O(2^k ε^1/5) and (1/ρ)^O(k) ε^1/8 in the respective settings.
- Applications: The Majority Is Stablest theorem supplies a hardness-of-approximation connection for Max-Cut, with a hardness ratio approximately .8787 near the Goemans–Williamson constant .8786.The connection proceeds through Dictator-vs.-No-Notables tests.
Index
The index catalogs the textbook’s principal concepts, theorems, algorithms, applications, and terminology across Boolean and Gaussian function analysis. It spans Fourier methods, influences, hypercontractivity, invariance principles, isoperimetry, learning, and approximation.
- Probability and analysis: Invariance Principles and Berry–Esseen variants are indexed for sums of random variables, vectors, Gaussian polynomials, and general product spaces.These entries place invariance methods alongside anticoncentration, concentration, and central-limit results.
- Applications: Applications indexed include property testing, learning theory, derandomization, circuit complexity, CSPs, Max-Cut, and hardness of approximation.The index records algorithms and tests such as Goldreich–Levin, Kushilevitz–Mansour, BLR, and Dictator-vs.-No-Notables.
- Foundations: The index covers foundational representations and analytic tools including Fourier expansions, Fourier coefficients, influences, noise operators, and orthogonal decompositions.Entries include Fourier analysis, Fourier basis, Fourier weight, influence, ANOVA decomposition, and the noise operator.
- Core theorems: Major structural results include the KKL, Friedgut Junta, Majority Is Stablest, FKN, and Gotsman–Linial theorems.These entries connect influence, noise stability, juntas, polynomial threshold functions, and Fourier structure.
- Gaussian analysis: Gaussian analysis entries include Gaussian space, noise operators, Hermite expansions, Gaussian surface area, and the Gaussian Isoperimetric Inequality.The index also references Borell’s theorem and Gaussian Minkowski content.
- Core theorems: It lists hypercontractivity in uniform, biased, general product-space, reverse, and two-function forms.The index also records related inequalities and induction results.