Analysis of Boolean Functions

Preface to the arXiv edition

• The May 2021 revision fixes 100+ small typos and errors and makes the book available on arXiv, with essentially no new mathematical content.The theorem, definition, and exercise numbering is unchanged; the book remains a snapshot of the field circa 2014.Source: Preface to the arXiv edition · p. 9

Preface to the first edition

• The book develops the foundations of analysis of Boolean functions and surveys applications through chapter highlights across property testing, social choice, cryptography, circuit complexity, learning theory, pseudorandomness, hardness of approximation, concrete complexity, and random graph theory.The subject studies Boolean functions f : {0,1}^n →{0,1} via Fourier expansion and other analytic means, with relevance to theoretical computer science and several mathematical fields.Source: Preface to the first edition · p. 9
• The book serves as a research reference or one-semester graduate course, and provides nearly 500 chapter-end exercises.The author’s Carnegie Mellon courses covered most of Chapters 1–5 and 7, parts of Chapters 6, 8, 9, and 11, and additional additive combinatorics.Source: Preface to the first edition · p. 10

Boolean functions and the Fourier expansion

• The chapter develops Fourier analysis as a way to extract information from Boolean functions and illustrates basic formulas with the Blum–Luby–Rubinfeld linearity test.Source: Boolean functions and the Fourier… · p. 19, §1.1 · p. 20

1.1. On analysis of Boolean functions

• Boolean functions map binary strings to bits and arise across computer science and mathematics; Fourier analysis is especially relevant when Hamming distance or uniform counting matters.Source: §1.1 · pp. 19–20

1.2. The “Fourier expansion”: functions as multilinear polynomials

• Every real-valued function on {−1,1}^n has a unique multilinear-polynomial Fourier expansion, with coefficients indexed by subsets of [n].The expansion may have up to 2^n terms.Source: §1.2 · p. 22

1.3. The orthonormal basis of parity functions

• The 2^n parity functions form an orthonormal basis for real-valued functions on {−1,1}^n, giving every function a unique linear combination of parities.Source: §1.3 · pp. 23–24

1.4. Basic Fourier formulas

• Fourier coefficients are uniform expectations E[f(x)χS(x)]; Plancherel recovers inner products from coefficients, Boolean correlation equals 1−2dist(f,g), and the mean is the empty-set coefficient.A Boolean function is unbiased exactly when it takes value 1 on half the Hamming cube.Source: §1.4 · pp. 25–26
• For Boolean-valued f, variance is 1−E[f]^2, equals its Fourier weight on nonempty sets, and is 1 when unbiased and 0 when constant.More generally, variance is proportional to distance from being constant, with 2ε ≤ Var[f] ≤ 4ε in Proposition 1.15.Source: §1.4 · p. 27
• Fourier weight on a set is the squared Fourier coefficient; for Boolean-valued functions these weights form a probability distribution called the spectral sample, and degree groups sets by cardinality.Parseval gives Boolean-valued functions total Fourier weight 1.Source: §1.4 · pp. 27–28

1.5. Probability densities and convolution

• Convolving two probability densities gives the distribution of the sum of independent draws, and convolution multiplies their Fourier coefficients.The convolution of densities ϕ and ψ is itself a probability density.Source: §1.5 · p. 30

1.6. Highlight: Almost linear functions and the BLR Test

• The BLR test uses three queries, and high acceptance implies that f is ε-close to a linear function; for small ε, the sharper bound is ε/3 and is sharp.Blum, Luby, and Rubinfeld test the relation f(x)+f(y)=f(x+y) on independently chosen x and y.Source: §1.6 · pp. 32–33
• The BLR test does not identify which linear function is close, but when f is ε-close to χS, two queries can locally recover χS(x) with high probability.The procedure samples y and outputs f(y)f(x+y).Source: §1.6 · p. 33
• The BLR highlight contrasts outputting f(x), which matches χS on most inputs, with local correction that determines χS(x) with high probability for every x.Source: §1.6 · p. 33

1.7. Exercises and notes

• The exercises ask readers to compute Fourier expansions for Boolean functions including minimum, point and density functions, inner product mod 2, equality, and not-all-equal.Source: §1.7 · pp. 33–34
• Other problems address uniqueness of Fourier expansions, degree, and the granularity of Boolean functions’ Fourier spectra.Source: §1.7 · pp. 35–36
• The exercises describe computing the Walsh–Hadamard transform using n2^n additions and subtractions instead of 2^(2n), and identify it as the method of choice for large n.Source: §1.7 · pp. 36–37
• The exercises ask when n queries are necessary and sufficient to identify a linear function, and study lower bounds on BLR-test rejection for functions close to characters.Source: §1.7 · p. 38
• Affine-function problems ask for characterizations and four-query tests, including a version with three uniformly distributed inputs and one nonrandom input.Source: §1.7 · p. 38
• The final problems define permutation-isomorphism and ask readers to verify a canonical form built by lexicographically maximizing successive degree-k Fourier-coefficient sequences.Source: §1.7 · p. 39
• Walsh introduced an orthonormal basis for Fourier expansion; Bonami’s symmetric character viewpoint and hypercontractivity helped shape the field, and Kahn, Kalai, and Linial ushered in renewed sophistication in theoretical computer science.Source: §1.7 · pp. 39–40

Basic concepts and social choice

• The chapter introduces influences and noise stability, motivates concepts through social choice, and concludes with Kalai’s Fourier-based proof of Arrow’s Theorem.Source: Basic concepts and social choice · p. 43

2.1. Social choice functions

• Boolean functions are framed as two-candidate voting rules, with majority and weighted majority (linear threshold) functions as examples.Source: §2.1 · pp. 43–44

2.2. Influences and derivatives

• Influence measures the probability that changing one coordinate changes the function’s output, and equals the sum of Fourier weights on sets containing that coordinate.For monotone Boolean functions, influence also equals the corresponding degree-1 Fourier coefficient.Source: §2.2 · pp. 46, 48
• Every coordinate of a monotone transitive-symmetric Boolean function has influence at most 1/sqrt(n).The proof uses the equality between influence and the degree-1 Fourier coefficient for monotone functions, and the equality of those coefficients across coordinates.Source: §2.2 · p. 48

2.3. Total influence

• Total influence is average sensitivity and tracks the Hamming-cube edge boundary; it is 0 for constants, n for parity, and 1 for dictators.Source: §2.3 · pp. 49–50
• For odd n, majority uniquely maximizes the sum of degree-1 Fourier coefficients, which measures expected votes agreeing with the election outcome.Source: §2.3 · pp. 50–51
• The Poincaré inequality has equality only for constants or dictators among Boolean functions, and implies an edge-boundary lower bound for half-measure sets.Source: §2.3 · p. 52

2.4. Noise stability

• In the voting-noise model, outcome agreement has probability 1/2 + 1/2 Stabρ[f], and majority’s noise stability or sensitivity has a limit as n grows at fixed noise.Source: §2.4 · pp. 53–54
• The noise operator scales degree-k Fourier coefficients by ρ^k, making noise stability a degree-attenuated sum; among unbiased Boolean functions, only dictators and their negations maximize it for 0 < ρ < 1.The attenuation decreases exponentially with degree.Source: §2.4 · pp. 55–56

2.5. Highlight: Arrow’s Theorem

• When Var[f] ≤ 1, only at most 1/(δε) coordinates have (1−δ)-stable influence at least ε, unlike ordinary influence, which can mark every parity coordinate as notable.Source: §2.5 · p. 57
• A unanimous rule that always yields a Condorcet winner must be a dictatorship; a cycle occurs when the three pairwise outcomes are all equal.The Fourier argument forces all weight onto degree 1, so the rule is a dictator or negated dictator; unanimity excludes the negated case.Source: §2.5 · pp. 58–59
• Under impartial culture, the chance of a Condorcet winner is linked to the rule’s noise stability at correlation -1/3.Voters independently choose uniformly among six rankings, and a winner occurs exactly when the three pairwise outcomes satisfy NAE3.Source: §2.5 · p. 59
• With all individual influences equal, the probability of a Condorcet winner is at most 91.9% asymptotically; majority attains the tight value 3/(2π) arccos(-1/3).The stated upper bound is 7/9 + 4/(9π) + o_n(1).Source: §2.5 · p. 60
• For any voting rule, the probability of a Condorcet winner is at most 7/9 + 2/9 W1[f].This bound supports the robust result: if the probability is 1 - ε, then f is O(ε)-close to ±χ_i for some coordinate i.Source: §2.5 · p. 60

2.6. Exercises and notes

• Exercise 2.56 asks about optimal agreement in correlation distillation, including a three-party success probability of 1/2 + 1/2ρ and an optimal solution f1 = ±χi.The exercise sets up parties with independently noised copies and requires each output to be unbiased.Source: §2.6 · p. 66
• The notes trace explicit study of noise stability to Benjamini, Kalai, and Schramm [BKS99], and the noise operator to Bonami and Beckner.They note that Kahn, Kalai, and Linial standardized the notation Tρ.Source: §2.6 · p. 68
• The notes credit the Fourier approach to Arrow’s Theorem and Theorem 2.57 and Corollary 2.60 to Kalai, and the FKN Theorem to Friedgut, Kalai, and Naor.They also attribute polarizations to Kleitman, the cube-embedding theorem to Enflo, and the Khintchine–Kahane theorem to Latała and Oleszkiewicz.Source: §2.6 · p. 68

3.1. Low-degree spectral concentration

• Small total influence yields low-degree concentration; Tribes is .01-concentrated up to degree O(log n), while majority is .01-concentrated up to O(1) despite influence Θ(√n).The Tribes example uses n = w2^w; the majority example shows there is no simple converse from concentration to small total influence.Source: §3.1 · pp. 69–70
• For Boolean f and δ ∈ (0,1/2], noise sensitivity gives ε-concentration up to degree 1/δ, with ε = 2/(1−e^−2) NS_δ[f] ≤ 3 NS_δ[f].For majority, the text also states δ-concentration up to degree 1/δ, equivalently ε-concentration up to degree 9/ε^2.Source: §3.1 · p. 70
• A Boolean function of degree at most k is a k2^(k−1)-junta, so constant-degree Boolean functions depend on a bounded number of coordinates.The proof uses the fact that each nonzero influence is at least 2^(1−k), together with the total-influence bound.Source: §3.1 · p. 70, §3.2 · p. 71

3.2. Subspaces and decision trees

• A nonzero real function of degree at most k is nonzero on at least a 2^−k fraction of inputs, implying each nonzero influence of a degree-k Boolean function is at least 2^(1−k).Thus each coordinate’s influence is either zero or at least 2^(1−k).Source: §3.2 · p. 71
• The section represents the domain as F_2^n, indexes Fourier characters by vectors in F_2^n, and introduces spectral p-norms.In this indexing, the zero vector denotes the constant-one character and e_i denotes the ith dictator.Source: §3.2 · pp. 71–72
• For an affine subspace of codimension k, its indicator has Fourier sparsity 2^k, is 2^-k-granular, and has Fourier L∞ norm 2^-k and L1 norm 1.Conjunctions of parity conditions indicate affine subspaces (or the zero function); coordinate equalities yield subcubes.Source: §3.2 · p. 73
• A size-s decision tree partitions inputs into subcubes, and its spectrum is ϵ-concentrated on degrees up to log(s/ϵ).Each root-to-leaf path defines a subcube, and the path subcubes partition the input space.Source: §3.2 · p. 74

3.3. Restrictions

• Fixing coordinates in a subcube restriction combines original Fourier terms containing the retained monomial after substituting fixed bits; in the example, the resulting x1 coefficient is 1/2.For the restriction x3 = 1, x4 = −1, the example computes that coefficient by summing the corresponding substituted terms.Source: §3.3 · p. 75
• Affine-coset restrictions require an explicit representative; translating by z multiplies each Fourier coefficient at γ by (−1)^(γ·z).A coset need not have a canonical representative, so the text treats restriction as translation followed by restriction to the subspace.Source: §3.3 · pp. 77–78

3.4. Learning theory

• Computational learning theory studies how to use examples (x, f(x)) from an unknown function to construct a hypothesis that predicts its values on future inputs.Source: §3.4 · p. 78
• If a target’s spectrum is ϵ/2-concentrated on a known collection F, random-example access suffices to learn it with error ϵ in time poly(|F|,n,1/ϵ).The learner estimates the coefficients indexed by F and takes the sign of the resulting approximate Fourier expansion.Source: §3.4 · pp. 79–80
• If every function in a class is ϵ/2-concentrated on degrees at most k, random examples yield learning with error ϵ in time poly(n^k,1/ϵ).The Low-Degree Algorithm takes all subsets of size at most k as F.Source: §3.4 · p. 81
• The Low-Degree Algorithm learns classes with influence at most t in time n^O(t/ϵ), and monotone functions in time n^O(√n/ϵ), from random examples with error ϵ.Source: §3.4 · p. 81
• Low-degree concentration also gives random-example learning in time poly(n^(1/δ),1/ϵ) for classes with NS_δ[f] ≤ ϵ/6, and n^O(log(s/ϵ)) for decision-tree size at most s.Source: §3.4 · p. 82
• Degree-k Boolean functions, including depth-k decision trees, can be learned exactly from random examples in time n^k · poly(n,2^k).Source: §3.4 · p. 82

3.5. Highlight: the Goldreich–Levin Algorithm

• With query access, the Goldreich–Levin algorithm runs in poly(n,1/τ) time and outputs sets whose Fourier coefficients have magnitude at least τ/2.It uses divide-and-conquer bucketing: repeatedly splits sets and discards buckets whose estimated Fourier weight is too small.Source: §3.5 · pp. 83–85
• If every class member’s spectrum is ϵ/4-concentrated on at most M sets, query access enables learning with error ϵ in time poly(M,n,1/ϵ).The Kushilevitz–Mansour algorithm applies to concentration on any small set collection, unlike the Low-Degree Algorithm’s low-degree requirement, but needs queries rather than random examples.Source: §3.5 · p. 83

3.6. Exercises and notes

• An exercise asks readers to show how Fourier coefficients transform under an invertible linear map and to consider affine or noninvertible maps.Source: §3.6 · pp. 85–86
• Exercises investigate Fourier norms, restrictions, sparsity, and concentration, including bounds and stability of Fourier spectra.They ask readers to prove that restrictions reduce spectral 1-norm and Fourier sparsity, and that a small L2 approximation preserves concentration up to a stated bound.Source: §3.6 · pp. 86–87
• Exercises explore uncertainty and spectral structure, including an uncertainty principle relating the supports of a function and its Fourier transform.Other problems concern Fourier L1 bounds for indicators of non-affine sets and the maximum possible Fourier L1 norm under an L2 constraint.Source: §3.6 · pp. 86–87
• Exercises define subcube partitions, parity decision trees, and affine-subspace partitions as generalized decision-tree models, and ask how their complexity measures relate.The problems compare size and depth or codimension across these models and examine extensions of a proposition about decision trees.Source: §3.6 · p. 88
• Decision-tree exercises connect depth and size with polynomial degree, Fourier coefficients, and influence, including examples where degree and tree complexity differ.One problem asks readers to establish degree 2 and decision-tree depth 3 for Equ3, then degree 2d and depth 3d for its d-fold product.Source: §3.6 · pp. 87–89
• Learning exercises cover exact learning from examples or queries, low-degree Fourier methods, and the Goldreich–Levin algorithm.Prompts include learning with zero error from random examples, learning classes such as juntas and low-Fourier-sparsity functions, and extending Goldreich–Levin to bounded real-valued functions.Source: §3.6 · pp. 89–90
• The notes trace Fourier-based learning to Linial, Mansour, and Nisan, noise sensitivity to Klivans, O’Donnell, and Servedio, and related algorithms to Goldreich and Levin and Kushilevitz–Mansour.Source: §3.6 · p. 92

DNF formulas and small-depth circuits

• Small DNFs and constant-depth circuits generalize decision trees, and their strong Fourier concentration is one reason they are central to explicit lower-bound study.Source: DNF formulas and small-depth circuits · p. 93

4.1. DNF formulas

• A decision tree of size s and depth k has an equivalent DNF and CNF, each of size at most s and width at most k.The DNF terms correspond to root-to-leaf paths ending at 1, and the CNF clauses to paths ending at 0.Source: §4.1 · p. 94
• A width-w DNF has total influence at most 2w, so its Fourier spectrum is ε-concentrated through degree 2w/ε.The dependence on ε can be improved later in the chapter.Source: §4.1 · p. 95
• A size-s DNF is ε-close to one of width log(s/ε), yielding Fourier concentration through degree O(log(s/ε)/ε).The text notes that the dependence on ε in this concentration bound will be improved later.Source: §4.1 · pp. 95–96

4.2. Tribes

• With its chosen parameters, Tribes_n is essentially unbiased and has total influence (ln n)(1 ± o(1)); the KKL theorem shows this example is tight up to constants for unbiased rules.The section also records a formula for its Fourier coefficients, but the supplied passage does not include the formula.Source: §4.2 · pp. 96–97

4.3. Random restrictions

• A δ-random restriction scales expected total influence by δ, and random restrictions reduce size-s DNF total influence to O(log s).The restriction leaves each coordinate free independently with probability δ and otherwise fixes it to either sign with probability (1−δ)/2.Source: §4.3 · pp. 98–99

4.4. Håstad’s Switching Lemma and the spectrum of DNFs

• Håstad’s Switching Lemma makes it exponentially unlikely in k that a δ-random restriction fails to convert a width-w DNF or CNF into a decision tree of depth less than k when δ ≪ 1/w.The bound has no dependence on the formula’s size or on n.Source: §4.4 · p. 100
• Width-w DNFs have Fourier spectrum ϵ-concentrated up to degree O(w log(1/ϵ)), and have small Fourier 1-norm at low degree.These bounds combine Håstad’s Switching Lemma with results on decision trees and random restrictions.Source: §4.4 · pp. 101–102
• For width-w DNFs with w ≥ 2, the spectrum is ϵ-concentrated on at most w^{O(w log(1/ϵ))} Fourier coefficients.For width O(log n) and constant ϵ, the collection has size n^{O(loglog n)}; for size-s DNFs the bound is (s/ϵ)^{O(loglog(s/ϵ)·log(1/ϵ))}.Source: §4.4 · p. 102

4.5. Highlight: LMN’s work on constant-depth circuits

• Depth-d circuits of size s have Fourier spectrum ϵ-concentrated up to degree O(log(s/ϵ)^(d−1)·log(1/ϵ)), by the LMN Theorem.Håstad later sharpened the degree bound to O(log(s/ϵ)^(d−2)·log(s)·log(1/ϵ)).Source: §4.5 · p. 106
• Depth-d circuits of size s have total influence I[f] ≤ O(log s)^(d−1).The bound yields size at least 2^{n·Ω(1)} for any constant-depth circuit computing majority.Source: §4.5 · pp. 106–107
• Depth-d polynomial-size circuits can be learned from random examples to error ϵ = 1/poly(n) in time n^{O(log n)^d}.The text summarizes this as quasipolynomial-time learnability of AC0.Source: §4.5 · p. 106
• A depth-d circuit agreeing with parity on at least 1/2+ϵ0 of inputs must have size at least 2^{Ω(n^(1/(d−1)))} for any constant ϵ0 > 0.The text notes this is close to tight, since parity has depth-d circuits of size n^{2n^(1/(d−1))}.Source: §4.5 · p. 107
• AC0-computable functions cannot serve as pseudorandom function generators, since a two-query test accepts with probability I[h]/n, at most polylog(n)/n for AC0 functions.For a uniformly random function, the same test accepts with probability 1/2.Source: §4.5 · p. 107

4.6. Exercises and notes

• The end-of-chapter exercises cover DNF/CNF representations and duality, monotone formulas, Fourier norms and concentration, learning, switching lemmas, and parity.Examples include exercises on Fourier 1-norms of read-once DNFs and parity’s DNF/CNF size.Source: §4.6 · pp. 107–108
• Circuit exercises ask for a depth-3 circuit of size O(n^1/2)·2^n^1/2 computing χ_[n], and linear-size De Morgan circuits for AND and parity.They also define De Morgan circuits and ask for a linear-size circuit for the complete quadratic function.Source: §4.6 · pp. 108–109
• Other exercises invoke KKL to show transitive-symmetric functions of variance Ω(1) have influence Ω(log n), and ask for a CNF-size lower bound for Tribes and a junta–Tribes distance bound.The junta exercise specifies that every 3/4 n-junta is ε0-far from Tribes_n for a universal ε0 > 0 and n > 1.Source: §4.6 · p. 109
• An exercise uses a permutation-and-seed algorithm that outputs satisfying assignments of width-w CNFs to derive the bound I[f] ≤ w.The algorithm forces variables when clauses become unit clauses and otherwise assigns seed bits; the exercise asks to deduce the influence bound.Source: §4.6 · p. 109
• A random monotone DNF exercise constructs a monotone function with sensitivity at least c′√n on a c′ fraction of inputs, and asks how this differs from majority.The construction uses width √n and 2^√n terms; the exercise states that both functions have average sensitivity Θ(√n).Source: §4.6 · pp. 109–110
• An exercise asks for a proof of the Baby Switching Lemma with constant 3, bounding the probability of a bad δ-random restriction by 3δw.Its proof outline pairs bad restrictions with extensions and bounds how often each extension can occur.Source: §4.6 · p. 110
• Mansour’s Conjecture dates to 1994; its weaker version would enable query-efficient learning of polynomial-size DNF, while Gopalan, Kalai, and Klivans showed it implies agnostic learning.Jackson obtained the non-agnostic learning result by a different method; Theorems 4.24 and 4.25 are also due to Mansour.Source: Notes · p. 111

Notes.

• The notes attribute random restrictions to Subbotovskaya, the LMN Theorem to Linial, Mansour, and Nisan, and the strongest known approximate-parity AC0 lower bound to Impagliazzo, Matthews, and Paturi and independently Håstad [Hås12].They also credit Theorems 4.20 and 4.30 to Boppana, noting that Linial, Mansour, and Nisan had proved a weaker bound.Source: Notes · p. 111

5.1. Linear threshold functions and polynomial threshold functions

• For every LTF f on {−1,1}^n with values in {−1,1}, W≤1[f] ≥ 1/2; the stronger 2/π bound for every LTF is an open conjecture.Source: §5.1 · pp. 114–115
• Functions with low noise sensitivity are close to low-degree PTFs; degree-k PTFs are determined by Fourier coefficients through degree k and satisfy W≤k[f] ≥ e^-2k.The stated lower bound cannot be improved beyond 2^(1-k).Source: §5.1 · pp. 115–116
• Sparse polynomial approximation yields sparse PTF representations, and the inner product mod 2 function requires huge threshold-of-parities circuits.The section also notes that sparse LTFs need not have small Fourier 1-norm, using majority as an example.Source: §5.1 · pp. 117–118

5.2. Majority, and the Central Limit Theorem

• The Central Limit Theorem, made quantitative by Berry–Esseen bounds, is used to estimate majority’s total influence and noise stability and extends to other linear threshold functions.For random sums, the Gaussian approximation applies when no coefficient is too large; the section gives an explicit error bound for majority’s influence estimate.Source: §5.2 · pp. 118–120
• For majority, the 2-dimensional CLT reduces the limiting noise-stability calculation to a Gaussian probability, and Sheppard’s Formula completes the justification of formula (5.5).The derivation uses the symmetry of the two quadrants and the convexity needed to apply the 2-dimensional CLT.Source: §5.2 · p. 120, §5.3 · p. 121

5.3. The Fourier coefficients of Majority

• The Majority Is Stablest Theorem says that unbiased functions with sufficiently small maximum influence have noise stability at most that of majority.The full theorem is deferred to Chapter 11; the text says it proves the result for sufficiently small ρ in Section 5.4.Source: §5.3 · p. 121
• Majority’s Fourier coefficients vanish at even degrees, while each fixed odd-degree Fourier weight converges to a constant as n tends to infinity.The text also gives an explicit coefficient formula and an error bound for fixed odd-degree weights.Source: §5.3 · pp. 122–123

5.4. Degree-1 weight

• The Level-1 Inequality bounds the degree-1 weight of a Boolean function with mean α ≤ 1/2; its sharp form is W1[f] ≤ 2α^2 ln(1/α).The text says this makes small subsets of the Hamming cube have unusually small degree-1 weight; Hamming balls asymptotically maximize it among small-volume sets.Source: §5.4 · p. 126
• Among functions with all first-level Fourier coefficients bounded by ε, degree-1 weight is at most 2/π; unbiased low-influence LTFs attain this bound.The text identifies this as the Majority Is Stablest Theorem in the limit ρ → 0+.Source: §5.4 · p. 127, The 2 · p. 127

The 2

• To prove the degree-1 bounds, the argument upper-bounds E[f(x)L(x)] by assigning f=1 to the α fraction where L is largest, then uses Hoeffding’s bound and the CLT to approximate L by a Gaussian when coefficients are small.For α = 1/2, the threshold is zero.Source: The 2 · p. 127
• If a Boolean function has |E[f]| ≥ 1−δ, then W1[f] ≤ 4δ^2 log(2/δ); assuming FKN holds with closeness Cδ strengthens its bound to δ/4+η.Here η = 16C^2δ^2 max(log(1/Cδ),1).Source: The 2 · p. 129

5.5. Highlight: Peres’s Theorem and uniform noise stability

• Peres’s Theorem establishes that the class of linear threshold functions is uniformly noise-stable.The section connects uniform noise stability to Fourier concentration at constant degree and learning from random examples; for LTFs, the stated degree cutoff is O(1/ϵ^2) and the learning time is n^O(1/ϵ^2).Source: §5.5 · pp. 130–131
• Compositions of s linear threshold functions are learnable in time n^O(s^2/ϵ^2), including the case of an AND of two LTFs.The section says this approach is the only known way to show that an AND of two LTFs is learnable with error .01 in polynomial time.Source: §5.5 · p. 131
• For degree-k polynomial threshold functions, known influence bounds imply uniform noise stability, and Kane’s theorem gives a further bound on their total influence.The stated bounds include I[f] ≤ O(n^(1−1/2k)) and I[f] ≤ 2^O(k)n^(1−1/O(k)); the Gotsman–Linial conjecture proposes the stronger bound I[f] ≤ O(k)√n.Source: §5.5 · pp. 133–134

5.16 (a) Show that in the Berry–Esseen Theorem we can also conclude

• Titsworth first computed the Fourier expansion of Majn; later work treated its asymptotics and the Kravchuk polynomials.The notes also credit Kalai with early asymptotics for Wk[Majn], with error bounds from O’Donnell [O’D03], and identify Kravchuk as introducing the polynomials.Source: §5.16 · p. 140
• The notes attribute Peres’s Theorem to [Per04], trace uniform noise stability to [BKS99], and cite Kane for improved influence bounds in some superconstant-degree cases.The [BKS99] bound on LTF noise sensitivity was O(δ^1/4), worse than Peres’s; Kane’s bound is I[f] ≤ poly(k)n^(1−1/O(k)).Source: §5.16 · p. 141

Pseudorandomness and F2-polynomials

• The chapter treats pseudorandomness as properties of fixed Boolean functions characteristic of random functions, including deterministic small-support probability-density constructions for derandomization.It also studies interplay between real-polynomial and F2-polynomial representations.Source: Pseudorandomness and F2-polynomials · p. 143

6.1. Notions of pseudorandomness

• A p-biased random Boolean function has all the stated properties with failure probability at most 2^-n, using Hoeffding bounds and a union bound over Fourier coefficients.For its Fourier coefficients, the notes distinguish the empty set coefficient, whose mean is p, from nonempty-set coefficients, whose mean is 0; the stated tail threshold is 2p(n^2)2^(-n/2).Source: §6.1 · pp. 143–144
• A function is ϵ-regular when every nonempty-set Fourier coefficient has absolute value at most ϵ.For probability densities, the corresponding notion is called ϵ-bias.Source: §6.1 · p. 144
• A function has (ϵ,δ)-small stable influences when each coordinate’s (1−δ)-stable influence is at most ϵ.This is also described as having no (ϵ,δ)-notable coordinates; when δ = 0, it means ϵ-small ordinary influences.Source: §6.1 · p. 145
• An (ϵ,k)-regular function has every nonempty Fourier coefficient on sets of size at most k bounded in absolute value by ϵ.For k = n or k = ∞, this is ϵ-regularity; a (0,k)-regular probability density is called k-wise independent.Source: §6.1 · pp. 146–147
• Restrictions of at most k coordinates change the mean of an (ϵ,k)-regular function by at most 2^kϵ; failure of regularity implies some such restriction changes it by more than ϵ.These two directions characterize (ϵ,k)-regularity.Source: §6.1 · p. 146
• Figure 6.1 compares the pseudorandomness notions, with arrows running from stronger notions to strictly weaker ones.The section also notes that these notions essentially coincide for monotone functions.Source: Figure 6.1 · p. 148, §6.1 · p. 148

6.2. F2-polynomials

• Every Boolean function has a unique F2-polynomial representation; parity has degree 1 over F2 but degree n in its real representation.F2 arithmetic represents XOR as addition and AND as multiplication.Source: §6.2 · pp. 148–149
• F2-degree never exceeds Fourier degree, and equals n exactly when the function is true on an odd number of inputs.The passage derives the F2 representation by reducing integer polynomial coefficients modulo 2, a step that cannot increase degree.Source: §6.2 · pp. 149–150
• For k-resilient f, deg_F2(f) ≤ n−k−1; for kth-order correlation-immune f, deg_F2(f) ≤ n−k.The resilient bound is stated for k < n−1, and the correlation-immune bound for k < n.Source: §6.2 · p. 150

6.3. Constructions of various pseudorandom functions

• Bent functions are 2^(−n/2)-regular and maximally distant from affine functions; every bent function of F2-degree at most 2 is obtained from the inner product mod 2 function by the stated transformations.The notes say that classifying all bent functions remains an open problem.Source: §6.3 · pp. 151–152
• For arbitrary g, the function f(x,y)=IP_2n(x,y)g(y) is bent.Here g maps n-bit inputs to {−1,1}.Source: §6.3 · p. 152
• A deterministic algorithm runs in poly(n/ϵ) time and outputs an ϵ-biased multiset of size at most 16(n/ϵ)^2.The construction uses a finite field and its linear encoding.Source: §6.3 · p. 153
• A row-span distribution is k-wise independent exactly when every nonempty sum of at most k columns of its matrix is nonzero; such a matrix exists with m=(k−1)ℓ+1 when n=2^ℓ≥k.The construction uses a Vandermonde matrix over a finite field.Source: §6.3 · p. 154
• A deterministic algorithm outputs an (ϵ,k)-wise independent multiset of size O(k log(n)/ϵ)^2 in poly(n/ϵ) time.Its distribution can be sampled using O(log k + log log(n) + log(1/ϵ)) independent random bits.Source: §6.3 · p. 155

6.4. Applications in learning and testing

• k-juntas can be exactly learned from random examples in time n^(3k/4)·poly(n), improving on the previously described n^k·poly(n) algorithm.The exponent can be replaced by ωk/(ω+1) when n × n matrices can be multiplied in O(n^ω) time; the algorithm balances finding a relevant coordinate against learning a low-degree F2-polynomial.Source: §6.4 · pp. 155–156
• The class of Boolean functions with Fourier 1-norm at most s is deterministically learnable from queries with error ϵ in time poly(n,s,1/ϵ).The result also applies to decision trees of size at most s.Source: §6.4 · pp. 158–159
• Functions with Fourier sparsity at most 2^O(k) are exactly learnable from queries in deterministic time poly(n,2^k).The stated example class includes decision trees of depth at most k.Source: §6.4 · p. 159
• The derandomized BLR test uses n+O(log(n/ϵ)) random bits rather than the original 2n, and acceptance probability 1−δ implies near-δ closeness to an affine function when ϵ ≪ δ.F2-linear functions are accepted with probability 1; the converse guarantees closeness to an affine, not necessarily linear, function.Source: §6.4 · p. 159

6.5. Highlight: Fooling F2-polynomials

• An ϵ-biased density supported on the inner-product-mod-2 function’s support has bias about 2^-n/2 yet gives that degree-2 function expectation 1 instead of about 1/2 under uniform input.Thus ϵ-bias alone does not guarantee fooling even degree-2 functions.Source: §6.5 · p. 160
• The d-fold convolution of an ϵ-biased density ϵ_d-fools all functions of F2-degree at most d, using O(d log n)+O(d2^d log(1/ϵ)) random bits.The proof proceeds by induction on degree using directional derivatives, which reduce degree by one.Source: §6.5 · pp. 161–162
• The d-fold convolution cannot in general fool degree-(d+1) functions, and whether the theorem’s error exponent can improve is unknown even for d=2.The passage identifies even a modest exponent improvement for d as large as log n as a major advance.Source: §6.5 · p. 163

6.6. Exercises and notes

• The problem set covers epsilon-biased and k-wise independent distributions, including constructions, support-size bounds, and applications to randomized matrix-product verification.It also asks for Fourier expansions and constructions of bent functions.Source: §6.6 · pp. 164–166
• Exercises relate F2-degree to support probability, Fourier sparsity and granularity, bent functions, and sharpness questions for resiliency and correlation immunity.They ask to prove that a nonzero degree-at-most-k F2 polynomial is nonzero with probability at least 2^-k, and that bent functions have degree at most n/2.Source: §6.6 · p. 165
• Other exercises develop exact learning of low-degree F2 polynomials and k-juntas, and establish properties of Gowers norms, including nonnegativity and norm behavior.The low-degree learning exercise specifies sample and running-time bounds, while the Gowers-norm exercises ask for monotonicity, the triangle inequality, and positivity for k at least 2.Source: §6.6 · pp. 167–169
• The notes state that explicit k-wise distributions of small support arose in orthogonal arrays, error-correcting codes, and derandomization, and that Alon, Babai, and Itai gave the construction in Theorem 6.32.The lower bound from Exercise 6.28 is essentially due to Rao.Source: §6.6 · p. 170
• The notes trace epsilon-regularity to Chung and Graham [CG92], small stable influences to Kahn, Kalai, and Linial [KKL88], and resilience and correlation immunity to foundational cryptography work.They identify with Corollary 6.14 and Theorem 6.25, and note that Corollary 6.14 is called the Xiao–Massey Theorem [XM88].Source: §6.6 · p. 170
• Siegenthaler’s 1984 theorem, motivated by cryptographic stream ciphers, captures the tradeoff between correlation-immunity and F2-degree.The notes explain that combining LFSR streams with functions correlated with input bits or tuples allows effective attacks.Source: §6.6 · p. 170
• The notes attribute Theorems 6.36, 6.42, and 6.44 to Mossel et al., Kushilevitz and Mansour, and Ben-Sasson et al., respectively.Bent functions were named and studied by Rothaus around 1966, published in 1976, and have applications in cryptography and coding theory.Source: §6.6 · pp. 170–171

Property testing, PCPPs, and CSPs

• The chapter centers on dictator testing, connects it to proof-assisted testing and CSPs as string-testing algorithms, and sketches Håstad’s optimal inapproximability results.It begins by extending BLR to a 3-query dictator test and says dictator tests translate into computational-complexity results for CSPs.Source: Property testing, PCPPs, and CSPs · p. 173

7.1. Dictator testing

• The NAE Test’s acceptance implies closeness to a signed dictator, and combining it with BLR yields a 6-query dictator tester with rejection rate .1.Acceptance probability 1−ϵ implies W1[f] ≥ 1−9ϵ/2 and, by the FKN Theorem, O(ϵ)-closeness to ±χi.Source: §7.1 · p. 176
• The randomized BLR+NAE Test is a 3-query local tester for dictators with rejection rate .05.It runs the BLR or NAE Test with probability 1/2 each.Source: §7.1 · p. 177
• Every subclass of dictators has a 3-query local tester with rejection rate .01, using BLR+NAE and local correction on the subset’s indicator string.The correction routine distinguishes dictators in the target subset from dictators outside it.Source: §7.1 · p. 177

7.2. Probabilistically Checkable Proofs of Proximity

• Any property can have a 3-query local tester when an appropriate proof is provided; the section generalizes testing from Boolean truth tables to strings.A Boolean function’s truth table is treated as a string of length 2^n, and string distance is relative Hamming distance.Source: §7.2 · p. 178
• PCPPs let testers query an input alongside proof bits: members have a proof accepted with probability 1, while inputs farther than ϵ from C are rejected for every proof with probability greater than λϵ.The proof is supplied as untrusted side information to help spot-check the input.Source: §7.2 · pp. 179–180
• A 3-query PCPP for odd parity uses an n−1-bit proof of partial sums and has rejection rate 1, although local testing requires n queries.Every string outside odd parity is at distance exactly 1/n, and at least one partial-sum check fails.Source: §7.2 · pp. 179–180
• Every property C ⊆ {0,1}^n has a 3-query PCPP with proof length 2^(2^n) and rejection rate .001.The proof establishes completeness and soundness for this system.Source: §7.2 · pp. 181–182
• A 3-query PCPP reduction for Max-CSP properties has proof length size(C)·polylog(size(C)) and positive rejection rate.This improves on reductions with proof length 2^poly(size(C)) and 2^(2^n).Source: §7.2 · p. 183

7.3. CSPs and computational complexity

• A CSP over domain Ω uses a finite set of predicate types; a Max-CSP instance is a multiset of constraints, and an assignment’s value is the fraction it satisfies.Each constraint applies a predicate to a scope of distinct variables.Source: §7.3 · pp. 184–186
• A CSP assignment is a string, and testing a uniformly sampled constraint accepts with probability equal to the assignment’s value; conversely, a tester yields a CSP, enabling PCPP descriptions as CSPs.The correspondence assumes finite tester randomness for the reverse direction; the text notes that general string testers may use irrational probabilities.Source: §7.3 · p. 187
• Max-Cut optimization is NP-hard, and finding optimal solutions is NP-hard for essentially all CSPs, motivating approximation guarantees for instances with high optimum value.An (α,β)-approximation outputs value at least α whenever the optimum is at least β; randomized algorithms need this guarantee in expectation.Source: §7.3 · p. 188
• The Max-E3-Lin constant assignments guarantee value at least 1/2, while Gaussian elimination is exact when the optimum is 1; Goemans and Williamson give a (.878β,β)-approximation for Max-Cut.The Max-E3-Lin guarantee is an efficient (1/2,β)-approximation for any β, and Gaussian elimination gives an efficient (1,1)-approximation.Source: §7.3 · pp. 188–189

7.4. Highlight: Håstad’s hardness theorems

• A uniformly random assignment satisfies 7/8 of Max-E3-Sat constraints in expectation, and Håstad [Hås01b] showed that for every constant δ > 0, it is NP-hard to (7/8 + δ,1)-approximate the problem.The text identifies this hardness result as the best possible efficient approximation guarantee, assuming P ≠ NP.Source: §7.4 · p. 190
• Håstad’s relaxed dictator tests accept dictators with high probability and reject functions with no notable coordinates; Theorem 7.40 converts such tests into UG-hardness for (α + δ,β − δ)-approximation.The reduction gives UG-hardness rather than NP-hardness and loses δ in the β parameter; the text says Håstad’s more complicated constructions remove both drawbacks for his theorems.Source: §7.4 · pp. 191–192
• The text gives relaxed tests using 3-literal OR predicates and 3-variable linear equations; for the latter, the BLR test accepts dictators but also accepts the constant-zero function and large parities with probability 1.The constant-one function can be addressed by replacing BLR with the Odd BLR Test.Source: §7.4 · pp. 192–193
• Adding noise to the Odd BLR test preserves high acceptance for dictators but suppresses large parities; the twist makes the constant-1 function pass only with probability 1/2.The test forms z=b·(x◦y), noises it to z′, and accepts when f(x)f(y)f(z′)=b.Source: §7.4 · pp. 193–194
• The Håstadδ test for Max-E3-Lin accepts dictators with probability 1−δ/2 and accepts functions with no notable coordinates with probability at most 1/2 when ε>δ.It is a (1/2,1−δ/2)-Dictator-vs.-No-Notables test.Source: §7.4 · pp. 194–195

7.5. Exercises and notes

• Exercises ask about amplifying local testers, query lower bounds, and constructing or combining tests for properties including equality, odd parity, and dictatorship.They also ask for rejection rates and parity acceptance probabilities for particular tests.Source: §7.5 · pp. 195–196
• Exercises show an efficient (α,β)-approximation yields an efficient (α,β)-distinguishing algorithm for Max-CSP(Ψ), give width-w CNF conversion of size at most (w−2)s for w≥3, and request affine-subspace PCPPs.The requested affine-subspace system has 3 queries, length-2n, and rejection rate a positive universal constant.Source: §7.5 · pp. 196–197
• Exercises develop randomized CSP assignments, relate predicate value to multilinear expansions, and ask how to round randomized assignments to ordinary ones.They also pose uniform-random assignment guarantees for Max-E3-Sat and Max-3-Lin.Source: §7.5 · pp. 198–199
• Further exercises extend dictator tests to real-valued and odd functions, and consider smoothing test inputs while controlling dictator acceptance.They ask about representing real-valued function queries as randomized bits and modifying tests while preserving their guarantees.Source: §7.5 · pp. 199–200
• Duplicating each variable into M copies and randomly selecting a copy per query preserves optimum, while deleting duplicate-scope constraints changes it by at most r^2/M and repairs the reduction.The deleted instance is a genuine Max-CSP(Ψ) instance, and r^2/M can be made arbitrarily small.Source: §7.5 · pp. 202–203
• Property testing began with Rubinfeld and Sudan, expanded through Goldreich, Goldwasser, and Ron, and local testability was introduced by Friedl and Sudan.Bellare, Goldreich, and Sudan first gave a local dictatorship tester, later rediscovered by Parnas, Ron, and Samorodnitsky; Kalai connected Arrow’s Theorem to dictatorship testing.Source: §7.5 · p. 203
• The PCPP definition was introduced independently in 2004 by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan and by Dinur and Reingold, building on earlier reductions and PCP work.The notes trace derivations of Theorems 7.19 and 7.18 to Arora et al. and Bellare, Goldreich, and Sudan, respectively.Source: §7.5 · p. 203
• A journal can use Theorem 7.20 to check a formalized proof by reading just 3 bits of the submitted proof and auxiliary proof, with completeness 1 and soundness implying a proof exists.If acceptance is at least 1−γ, the submitted string is 1-close to strings accepted by the proof-checking circuit; querying ⌈30/γ⌉ bits can raise confidence to 99.99%.Source: §7.5 · pp. 203–204
• The generic implication from Dictator-vs.-No-Notables tests to Unique-Games hardness is essentially due to Khot et al., with an explicit printed proof possibly first given by Austrin.The notes also identify Khot’s Unique Games Conjecture and describe Raghavendra’s almost-complete theory of optimal inapproximability under that conjecture.Source: §7.5 · p. 204

Generalized domains

• Product probability spaces extend the framework beyond {0,1}^n, but derivatives fail when coordinate domains have size greater than two and hypercontractivity depends on the distributions.The chapter assumes identical coordinate spaces and distributions for notational convenience; classic examples include p-biased hypercubes and abelian groups.Source: Generalized domains · p. 207

8.1. Fourier bases for product spaces

• A Fourier basis is an orthonormal basis containing the constant function, and taking all coordinatewise products of such a basis gives a Fourier basis for the product space.The resulting Fourier formulas are the same for every product Fourier basis, with a basis-independent development deferred to Section 8.3.Source: §8.1 · pp. 209–211

8.2. Generalized Fourier formulas

• Familiar combinatorial and probabilistic notions have Fourier formulas on product spaces that do not depend on the chosen Fourier basis.Because derivatives do not apply to general domains, coordinate influence is defined using the Laplacian; the section also extends noise operators, noise stability, and stable influences.Source: §8.2 · pp. 211, 213, 214, 215
• Degree is the least k for which f is a sum of k-juntas, and it equals the largest support size of a nonzero coefficient in any fixed product Fourier basis.A k-junta depends on at most k coordinates.Source: §8.2 · p. 215

8.3. Orthogonal decomposition

• The orthogonal decomposition assigns f a component for each coordinate set S; each component depends only on S and is orthogonal to functions on proper subsets, so distinct components are orthogonal.The components can be defined by inclusion-exclusion from coordinate projections.Source: §8.3 · pp. 216–218
• The decomposition also stratifies f by degree: its degree-k part sums the components indexed by sets of size k, and its degree-k weight is the squared norm of that part.The degree-k part is denoted f^=k and its weight Wk[f].Source: §8.3 · p. 220

8.4. p-biased analysis

• In p-biased analysis, each bit is independently −1 with probability p and 1 with probability q = 1 − p; the one-bit Fourier basis is {1, φ}, with mean parameter µ = 1 − 2p.The basis is centered and normalized; for a dictator, the constant and singleton Fourier coefficients are µ and σ, respectively, and all others are zero.Source: §8.4 · pp. 220–221
• A function's usual Fourier expansion can be converted to its biased expansion by substituting the biased basis functions; the selection function provides an example of this conversion.The text cautions that biased Fourier notation resembles the uniform case but does not in general have the same coefficients.Source: §8.4 · p. 221
• The Margulis–Russo Formula relates the rate of change of a Boolean function’s probability under π_p to its total influence.For monotone functions, this probability is strictly increasing in p when the function is nonconstant.Source: §8.4 · pp. 224–225
• Majority’s probability curve becomes increasingly step-like around p = 1/2 as n grows, illustrating a sharp threshold.The derivative at p = 1/2 equals the uniform-distribution total influence of Maj_n.Source: §8.4 · p. 225
• A sharp threshold roughly corresponds to superconstant total influence under the function’s critical probability distribution.The critical probability is where the probability that the function is True equals 1/2; the Margulis–Russo Formula links the slope there to total influence.Source: §8.4 · p. 226

8.5. Abelian groups

• On domains with at least three elements, abstract orthogonal decomposition is useful when equality is the only operation, while addition enables a canonical character basis.The section considers complex-valued functions on finite abelian groups under uniform, translation-invariant measure.Source: §8.5 · p. 227
• For finite abelian groups with uniform measure, characters form an orthonormal Fourier basis, and there are exactly |G| characters.For Z_m, the characters yield a Fourier basis; products of cyclic-group characters give the basis for finite abelian groups.Source: §8.5 · p. 228
• For functions on a finite abelian group, convolution transforms into pointwise multiplication of Fourier coefficients.The section identifies convolution as central to analysis on domains with addition.Source: §8.5 · p. 229
• For Fourier analysis on F_p^n, the characters are indexed using c in this setting, and the notions of affine subspaces and their restrictions generalize from p=2.The passage introduces this as a generalization of notation and notions from Chapters 3.2 and 3.3.Source: §8.5 · p. 229

8.6. Highlight: Randomized decision tree complexity

• Randomization gives RDT(Maj3)=8/3, while under a uniform input distribution the expected query cost is Δ(Maj3)=5/2, both below the deterministic worst-case cost of 3.The randomized tree formalism defines cost as the maximum, over inputs, of expected queries; Δ(f) minimizes average query cost over computing trees.Source: §8.6 · pp. 230–231
• For nonconstant monotone transitive-symmetric f, Theorem 8.66 lower-bounds Δ^(pc)(f); when pc=Θ(1/n) or 1−Θ(1/n), the bound is Δ^(pc)(f) ≥ Ω(n).The bound is strongest possible in those critical-probability regimes, including OR_n.Source: §8.6 · pp. 231–232
• For an infinite family of monotone transitive-symmetric functions with pc=1/2, Δ(f) ≤ O(n^2/3 log n) [BSW05].The theorem shows Theorem 8.66 can be tight up to a logarithmic factor when pc=1/2.Source: §8.6 · p. 232

8.7. Exercises and notes

• The exercises and notes include a prompt to generalize the definitions and results of Sections 8.1 and 8.2 to general finite product spaces L2(Ω1 ×···×Ωn,π1 ×···×πn).Other listed exercises verify inner-product, Fourier-expansion, and operator properties.Source: §8.7 · pp. 235–236

8.9 Prove Proposition 8.24. (Hint: Exercise 1.17.)

• Exercises extend noise-operator questions to L2(Ωn,π⊗n), including negative ρ for the uniform distribution on an m-element domain when ρ ≥ −1/(m−1).They also ask for bounds on ∥Li f∥p in terms of influences.Source: §8.9 · p. 236

8.13 Show that Definition 8.30 extends by continuity to Inf(0)

• Exercises on the extension of Definition 8.30 to Inf(0) address continuity, uniqueness, set-indexed components, and the Doob martingale for revealing coordinates one at a time.They also ask for conditional-expectation properties of the martingale differences and an L∞ bound on f =S.Source: §8.13 · pp. 236–237

Generalized domains

• Exercises 8.32–8.33 extend Fourier-analysis definitions and results to complex inner product spaces and vector-valued functions, including Plancherel; finite-range functions can be represented in a probability simplex.The finite-range representation uses the simplex in R^m and treats its vertices as the elements of the range.Source: §8.13 · p. 240
• Exercise 8.34 transfers linear threshold functions on product spaces to the usual Boolean cube, preserving correlated pairs and enabling application of Peres’s Theorem.The exercise defines a linear threshold function as the sign of a degree-at-most-one function.Source: §8.13 · p. 241
• Exercise 8.35 develops Fourier analysis on finite abelian groups: characters form a Fourier basis, and their group is the dual group, isomorphic to the original group.The following exercise asks to verify that convolution is associative and commutative and transforms to pointwise multiplication of Fourier coefficients.Source: §8.13 · p. 241
• Exercises 8.37–8.38 address decision-tree revealment, asking how transitive symmetry permits equal coordinate revealment without changing expected cost and how revealment is defined.For transitive-symmetric functions, the minimum possible maximum coordinate revealment is posed for characterization; related exercises give decision-tree cost bounds for iterated majority.Source: §8.13 · pp. 241–242

8.13 Show that Definition 8.30 extends by continuity to Inf(0)

• Fourier analysis extends to nonsymmetric functions through general orthogonal decompositions and also applies on finite and locally compact abelian groups.Efron and Stein proved Var[f] ≤ I[f] for symmetric f, and Steele extended the result to nonsymmetric f using the Fourier-basis approach. The p-biased hypercube is motivated by random graph and percolation theory; its Fourier analysis has been used to study threshold phenomena.Source: §8.13 · pp. 244–245

Basics of hypercontractivity

• Hypercontractivity bounds norms of noise-smoothed functions, and its special cases cover many applications while the full theorem’s proof is deferred to Chapter 10.The (2,q) and (p,2) theorems quantify smoothing; the latter gives a small-set expansion interpretation for the noisy hypercube graph.Source: Basics of hypercontractivity · pp. 247–248

9.1. Low-degree polynomials are reasonable

• A degree-k polynomial of independent uniform ±1 bits is 9^k-reasonable, and a corresponding bound holds for independent B-reasonable inputs.For independent inputs with mean and third moment zero, the bound is max(B,9)^k-reasonable when each input is B-reasonable; the Bonami Lemma also supports anticoncentration results and a proof of the FKN Theorem.Source: §9.1 · pp. 250–252

9.2. Small subsets of the hypercube are noise-sensitive

• The (2,4)-hypercontractivity result extends a low-degree fourth-moment bound to general functions, without requiring degree-k homogeneity.The text describes hypercontractivity as quantifying the smoothing effect of the noise operator.Source: §9.2 · p. 253
• For a set A of volume α, the 1/3-noisy hypercube leaves A with probability at least 1−α^1/2, a bound essentially sharp for Hamming balls.For a codimension-k subcube with α=2^-k, the probability of remaining in A is α^log(3/2)≈α^0.585≤α^1/2.Source: §9.2 · pp. 254–255
• For Boolean f, the 1/3-stable influence of coordinate i is at most Inf_i[f]^3/2.The section identifies this stable influence with the noise stability of the discrete derivative D_i f.Source: §9.2 · p. 255
• For a Boolean function of mean α, W_≤1[f]≤3α^3/2, and almost all its Fourier weight lies above degree 0.25log(1/α).The section notes that the level-k inequalities also yield bounds for larger k.Source: §9.2 · p. 256

9.3. (2, q)- and (p,2)-hypercontractivity for a single bit

• Independent (p,q,ρ)-hypercontractive random variables have a sum that is also (p,q,ρ)-hypercontractive.Self-adjointness also yields a dual norm inequality: an Lp-to-Lq bound for T implies an Lq′-to-Lp′ bound with the same constant.Source: §9.3 · p. 257, §9.4 · p. 259
• For a uniform ±1 bit, Theorem 9.17 establishes (2,q,ρ)-hypercontractivity for q>2, while Theorem 9.18 establishes (p,2,ρ)-hypercontractivity for 1≤p<2 under their stated parameter bounds.For q=6, the sharp condition is ρ≤1/√5.Source: §9.3 · pp. 257–258

9.4. Two-function hypercontractivity and induction

• The weak two-function hypercontractivity theorem applies when 0≤r,s≤1 and 0≤ρ≤prs, and restriction induction extends its one-coordinate case to product domains.The induction assumes the inequality on one coordinate and establishes it on Ω^n.Source: §9.4 · pp. 260–261
• Induction establishes weak two-function hypercontractivity, yielding the full (p,2) and (2,q) theorems; the inequality extends to product spaces when it holds on each factor.Source: §9.4 · p. 261

9.5. Applications of hypercontractivity

• Degree-k functions receive Bonami-type Lq bounds and the estimate ∥f∥2 ≤ e^k∥f∥1; in degree one, these imply Khintchine’s inequality.Source: §9.5 · p. 262
• Degree-k functions have tails exp(−Θ(t²/k)) beyond t standard deviations, generalizing the linear-form Chernoff decay.Theorem 9.24 also shows that a nonconstant degree-k function exceeds its mean with noticeable probability.Source: §9.5 · p. 263
• For a set A of volume α, a δ-noisy step from a uniformly random point in A returns to A with probability at most α^{δ/(1−δ)}.Hypercontractivity also yields level-k Fourier-weight bounds for indicators, including W1[f] ≤ 2α² ln(1/α) when k = 1.Source: §9.5 · p. 264

9.6. Highlight: The Kahn–Kalai–Linial Theorem

• For every unbiased Boolean function, Kahn, Kalai, and Linial show MaxInf[f] = Ω(log n/n).The theorem also scales with the function’s variance for biased functions.Source: §9.6 · p. 265
• If a monotone election’s mean is at least −.99, a candidate can force outcome 1 almost surely by bribing at most O(n/log n) voters; the symmetric condition holds for −1.Thus some candidate can produce 99% bias with an o(1) voter fraction; Ajtai and Linial show resistance to bribes of up to ϵn/log² n voters, changing expectation by at most O(ϵ).Source: §9.6 · pp. 265–266
• An unbiased function with total influence at most K has a coordinate with influence at least 2^{-O(K)}, the KKL edge-isoperimetric conclusion.Source: §9.6 · pp. 266–267
• For unbiased functions with total influence at most K, Friedgut’s Junta Theorem gives an approximation by a 2^O(K)-junta; low-degree Fourier concentration also yields a close junta.Theorem 9.28 gives a 2ε-close junta when the Fourier spectrum is ε-concentrated through degree k.Source: §9.6 · pp. 268–269
• Every Boolean function is ϵ-close to an exp(O(I[f]/ϵ))-junta, with its Fourier spectrum 2ϵ-concentrated on subsets of a coordinate set of that size.This is Friedgut’s Junta Theorem.Source: §9.6 · p. 269
• Linear threshold functions are ϵ-close to juntas on I[f]^(2+η)·(1/η)^O(1/ϵ²) coordinates; for constant ϵ, this yields I[f]^2·polylog(I[f]) coordinates, also for constant-degree PTFs.The LTF bound is essentially best possible: majority has influence Θ(√n) but is not .1-close to any o(n)-junta.Source: §9.6 · p. 269
• If Var[f] ≥ 1/2, some nonempty S with |S| ≤ O(I[f]) has Fourier coefficient squared at least exp(−O(I[f]^2)); improving this to exp(−O(I[f])) remains open.When Var[f] < 1/2, the empty Fourier coefficient squared is at least 1/2.Source: §9.6 · p. 270

9.7. Exercises and notes

• The exercises state that for Boolean f of mean α, W≤k[f] = o(α) as α → 0 when k ≤ .373 ln(1/α), and pose polynomial-time learning results for low-influence monotone functions.The learning exercises also cover monotone functions with polynomial decision-tree size.Source: §9.7 · p. 273
• The exercises note that KKL fails for functions into [−1,1] even with variance bounded below, and ask to show Friedgut’s exponential dependence on influence is necessary.Source: §9.7 · pp. 273, 275
• The exercises ask for a general-variance KKL Edge-Isoperimetric Theorem and bounds locating a large Fourier coefficient, with a stronger coefficient bound for nonconstant monotone functions.For the general nonconstant case, Exercise 9.32 gives |S| ≤ O(I[f]/Var[f]) and f̂(S)^2 ≥ exp(-O(I[f]^2/Var[f]^2)); Exercise 9.33 improves the exponent to -O(I[f]/Var[f]) for monotone functions.Source: §9.7 · p. 276
• Exercise 9.38 seeks to estimate |M| for a concrete improvement on Theorem 9.21; for q = 4 and k = 2, it gives |M| = 60.It also states C_{q,k} = Θ(1)·k^(-1/4+1/(2q)).Source: §9.7 · p. 278
• Paley established early hypercontractivity results, and Bonami gave a homogeneous-degree variant with constant 1 when q is even.Bonami’s combinatorial proof treated degree 2 and even q; the notes say it resembles the matching-counting approach in Exercise 9.37.Source: §9.7 · pp. 278–279
• Kiener and Schreiber independently extended hypercontractivity to homogeneous polynomials and general orthonormal random variables, respectively.Bonami’s thesis contains the full Hypercontractivity Theorem and a sharper combinatorial result, and extends the combinatorial proof to symmetric orthonormal random variables.Source: §9.7 · p. 279
• Gaussian hypercontractivity developed alongside the theory for bits: Nelson gave Gaussian results, and Gross derived hypercontractivity from log-Sobolev inequalities.The notes connect the Gaussian setting to the bit setting through the central limit theorem and describe Gross’s induction and transfer to the Gaussian case.Source: §9.7 · p. 280
• Talagrand explicitly proved the KKL Edge-Isoperimetric Theorem, while Exercise 9.30’s explicit lower bound on the KKL constant is the best known and remains a factor of 2 from the best known upper bound.The upper bound is achieved by the tribes function; the notes also state that no combinatorial proof of the KKL Theorem is known.Source: §9.7 · p. 281

hypercontractivity

• For finite product spaces whose outcomes each have probability at least λ, the General Hypercontractivity Theorem gives ∥T_ρ f∥_q ≤ ∥f∥_2 and ∥T_ρ f∥_2 ≤ ∥f∥_q′ for q > 2 within its stated range of ρ.The theorem extends consequences of the uniform-bit result with parameters depending on λ; randomization/symmetrization can sometimes remove that dependence, as in Bourgain’s Sharp Threshold Theorem.Source: hypercontractivity · p. 283

10.1. The Hypercontractivity Theorem for uniformly random bits

• For uniform ±1 bits, the full theorem follows by equivalence with its Two-Function form, induction across coordinates, and a one-bit inequality.The one-bit condition is ρ² ≤ (p−1)/(q−1), and the induction extends the inequality from individual coordinates to product spaces.Source: §10.1 · pp. 284, 286
• The Two-Function Hypercontractivity Theorem interpolates between Hölder’s bound for fully correlated inputs and the product-of-means bound for independent inputs.For Boolean-valued functions it also yields a two-set generalization of Small-Set Expansion, with b ≥ ρa required; the bound is essentially sharp for concentric Hamming balls.Source: §10.1 · pp. 284–285

10.2. Hypercontractivity of general random variables

• For mean-zero X with ∥X∥₂ = 1, the largest ρ giving (2,q,ρ)-hypercontractivity is within a q-dependent constant of 1/∥X∥q.The text states ρ = Θq(1/∥X∥q) is sufficient and ρ ≤ 1/∥X∥q is necessary.Source: §10.2 · p. 288
• Independent-sign randomization and symmetrization extend hypercontractivity bounds from symmetric random variables to general mean-zero variables.The symmetric-variable result is established using randomization, and the combined technique yields a (2,q)-hypercontractivity statement for mean-zero variables.Source: §10.2 · pp. 289–290
• For discrete random variables, the least atom probability λ controls the hypercontractivity parameter, whose λ-dependence is optimal; the sharp result is due to Latała and Oleszkiewicz, with Wolff’s reduction.The text states that the sharp parameter remains optimal even for two-valued variables.Source: §10.2 · p. 291
• For finite probability spaces with every outcome having probability at least λ, Corollary 10.20 gives both stated norm inequalities for q > 2 and 0 ≤ ρ ≤ 1.The General Hypercontractivity Theorem then follows by applying the Hypercontractivity Induction Theorem.Source: §10.2 · p. 292

10.3. Applications of general hypercontractivity

• General hypercontractivity bounds norms of low-degree functions and yields degree-k concentration, with the probability of exceeding t standard deviations decaying like exp(−Θ(t^2/k)).The constant in the concentration bound’s Θ(·) is linear in λ.Source: §10.3 · pp. 292–293
• The applications also include a small-set expansion generalization and a bound relating a coordinate’s stable influence to a power of its usual influence.The stable-influence theorem applies to Boolean functions on the product space described in Theorem 10.25.Source: §10.3 · p. 293
• The general-space KKL theorem lower-bounds maximum influence, and Friedgut’s theorem approximates a Boolean function by a junta of size (1/λ)^O(I[f]/ϵ).The KKL result also gives an average-influence lower bound when the normalized influence is sufficiently large relative to log n/log(1/λ).Source: §10.3 · pp. 294–295
• Monotone transitive-symmetric functions with critical probability in the stated interior range have sharp thresholds, but the restriction matters: OR_n is a counterexample outside that range.For OR_n, the probability of being true remains about 3/4 at bias 2pc, so it does not have a sharp threshold.Source: §10.3 · pp. 296–297

10.4. More on randomization/symmetrization

• Randomization/symmetrization multiplies each orthogonal Fourier level by an independent random sign; it preserves the 2-norm and bounds q-norms using noise-smoothed norms.For q ≠ 2, the section gives a pair of inequalities relating the function’s q-norm to those of its noise-smoothed versions.Source: §10.4 · pp. 297–299
• For q > 1, ∥f≤k∥q ≤ C_q^k∥f∥q, where C_q depends only on q, so low-degree projection increases norms by a space-independent factor.The proof uses randomization/symmetrization to transfer Boolean-cube bounds to general product spaces.Source: §10.4 · pp. 299–301

10.5. Highlight: General sharp threshold theorems

• At very small p, low total influence need not imply closeness to a junta: OR and the function detecting three consecutive −1s are counterexamples.The OR example has constant total influence at its critical probability, yet is not .1-close to any junta on o(n) coordinates.Source: §10.5 · p. 305
• For graph properties, Friedgut’s Sharp Threshold Theorem gives a low-influence characterization that applies even when p is very small.Friedgut extended the result to monotone hypergraph properties, including perfect matching in a random 3-uniform hypergraph and tautology of a random width-3 DNF.Source: §10.5 · pp. 305–306
• For any product probability space, Bourgain’s theorem says a {−1,1}-valued function with I[f] ≤ K and Var[f] ≥ .01 has a booster with |τ| ≥ exp(−O(K²)).The constants hidden in O(·) are absolute and independent of the underlying space and distribution.Source: §10.5 · p. 306
• For low-influence Boolean functions, Bourgain’s theorem yields small coordinate sets whose restrictions can act as boosters, and the result suffices to derive sharp-threshold results obtainable from Friedgut’s theorem.The theorem constructs input-dependent notable-coordinate sets of size at most exp(O(k)), with associated families of at most exp(O(k^2)) subsets; in the monotone small-p case, a set of size O(K) raises the probability by exp(−O(K^2)).Source: §10.5 · pp. 306, 307, 312
• The proof adapts Friedgut’s Junta Theorem with randomization and symmetrization, making notable coordinates depend on the input and controlling sets that may be unusually large.Low-degree functions are used as “reasonable” functions in handling the possible oversized sets.Source: §10.5 · pp. 307–308

10.6. Exercises and notes

• The exercises address hypercontractivity inequalities and derivations, including reverse hypercontractivity and its two-function form.They also ask about closure under sums of independent hypercontractive variables and converses for the two-point inequality.Source: §10.6 · pp. 313–314
• For positive f on {−1,1}, the Reverse Two-Point Inequality states that ||T_ρ f||_q ≥ ||f||_p when −∞ ≤ q < p ≤ 1 and 0 ≤ ρ ≤ p(1−p)/(1−q).The exercises extend the proof across parameter cases using the two-point inequality, monotonicity of norms, duality, and the semigroup property.Source: §10.6 · p. 315
• Wolff’s result says that, under ||T_ρ f||_2 = 1 on a finite probability space with atom probabilities at least λ, a minimizer of ||f||_p exists and takes at most two values.The exercise outlines a Lagrange-multiplier argument and uses strict concavity to show that the resulting equation has at most two solutions.Source: §10.6 · pp. 317–318
• The Latała–Oleszkiewicz result identifies the largest ρ for which ||T_ρ f||_2 ≤ ||f||_p holds on a biased two-point space.For 1 < p < 2 and 0 < λ < 1/2, the exercise exhibits the nonconstant sharp function f(x) = exp(−xu/p), where exp(−u) = λ/(1−λ).Source: §10.6 · pp. 318–319
• The exercises establish the Log-Sobolev Inequality 2 Ent[f^2] ≤ I[f] and give both a derivative-based proof and a direct proof by induction on product spaces.They also derive the Poincaré Inequality and an edge-isoperimetric bound that is off by a factor of ln 2 from the stated optimal inequality.Source: §10.6 · p. 320
• A further exercise extends the Log-Sobolev Inequality to general product-space domains.It specifies λ as the minimum outcome probability, λ′ = 1−λ, and exp(−u) = λ/λ′.Source: §10.6 · p. 321
• An exercise’s single-outcome example shows that Corollary 10.20 cannot hold for ρ > λ^(1/2−1/q).The example assigns probability λ to one outcome and defines f to be its indicator.Source: §10.6 · p. 321

Gaussian space and Invariance Principles

• For fixed volume, Hamming ball indicators have maximal noise stability among small-influence functions, as stated in the Majority Is Stablest framework.The theorem applies to mean-zero functions with small maximum influence, or more generally with no (ϵ,ϵ)-notable coordinates.Source: Gaussian space and Invariance Principles · p. 327
• The Invariance Principle shows that low-degree or uniformly noise-stable Boolean functions with small influences are approximable by Gaussian functions, enabling reduction to Borell’s Isoperimetric Theorem.It generalizes the Berry–Esseen Central Limit Theorem and roughly preserves distributions when independent mean-zero, variance-one random variables replace the Fourier variables.Source: Gaussian space and Invariance Principles · p. 328

11.1. Gaussian space and the Gaussian noise operator

• Gaussian functions can be simulated by sums of random bits in a way that preserves polynomial degree, allowing results to transfer between Boolean and Gaussian analysis.In particular, the majority function converges to the sign function on one-dimensional Gaussian space.Source: §11.1 · p. 329
• Pairs formed from ρ-correlated bit strings yield approximate Gaussians whose joint distribution converges to that of ρ-correlated Gaussians.Each variable has mean zero and variance one, and their covariance is ρ.Source: §11.1 · p. 329
• For 1 ≤ p ≤ ∞, the Gaussian noise operator is an Lp contraction; for −1 < ρ < 1 it smooths L1 functions, which it approximates in L1 as ρ → 1−.The operators also satisfy the semigroup identity Uρ1Uρ2 = Uρ1ρ2.Source: §11.1 · p. 331
• Gaussian hypercontractivity holds in Gaussian space as in the Boolean setting, with a standard one-function Lp-to-Lq form.The two-function theorem is stated for f and g in Gaussian Lp spaces; the one-function form follows as a corollary.Source: §11.1 · pp. 333–334
• The Ornstein–Uhlenbeck operator, also called the number operator, is introduced as the Gaussian analogue of the discrete Laplacian; in one dimension its formula is Lf(x) = x f′(x) − f′′(x).The differential formula assumes f is in the domain of L and is C3.Source: §11.1 · pp. 334–335
• Differentiating Gaussian hypercontractivity yields the Gaussian log-Sobolev inequality for functions in the domain of L.Source: §11.1 · pp. 335–336

11.2. Hermite polynomials

• The univariate Hermite polynomials form a complete orthonormal basis of L2(R,γ), obtained by orthogonalizing polynomials; products extend the basis to L2(Rn,γ).The Hermite polynomials are orthogonal, and the normalized polynomials form the stated basis.Source: §11.2 · pp. 336–338
• The Hermite polynomials form a complete orthonormal basis for L2(Rn,γ), so Gaussian functions admit Hermite expansions converging in L2(Rn,γ).Source: §11.2 · p. 338

Borell’s Isoperimetric Theorem (volume- 1

• For mean-zero functions with range [−1,1], halfspaces through the origin attain the Gaussian noise-stability upper bound; at volume 1/2 they also minimize noise sensitivity.Source: Borell’s Isoperimetric Theorem… · p. 340, §11.3 · p. 340

11.3. Borell’s Isoperimetric Theorem

• For ρ ∈ (0,1), Borell’s theorem [Bor85] bounds the noise stability of any [0,1]-valued Gaussian function of mean α by Λρ(α), the stability of a halfspace of volume α.The bound applies to functions in L2(Rn,γ).Source: §11.3 · pp. 340–341

2 Borell Isoperimetric Theorem. Fix θ ∈(0, π

• Rotation sensitivity and its subadditivity let the proof break a rotation into steps, establishing the stated Borell case for angles π/(2ℓ), ℓ∈N+.The corresponding correlations are cos(δ1 +···+δℓ) between endpoints and cosδj at each step.Source: §2 · p. 342

11.4. Gaussian surface area and Bobkov’s Inequality

• For equal-Gaussian-volume sets A and halfspaces H, Gaussian isoperimetry gives surfγ(A) ≥ surfγ(H).The section identifies this as a consequence of Borell’s theorem and states that the halfspace’s surface area is U(α) when its Gaussian volume is α.Source: §11.4 · p. 343
• The Gaussian surface-area definition is insensitive to measure-zero changes, unlike Minkowski content in general; for disjoint unions of closed, full-dimensional convex sets, the two agree.The section also gives an equivalent definition through an infimum over smooth approximations to the set indicator.Source: §11.4 · pp. 344–345
• For convex sets A in Rn, surfγ(A) ≤ O(n^1/4), and Nazarov’s bound is tight up to a constant; the section also reports bounds for other set classes.Those classes include intersections of k halfspaces, origin-apex cones, and degree-k polynomial threshold sets.Source: §11.4 · pp. 345–346
• Bobkov’s inequality yields U(E[1A]) ≤ surfγ(A) for Gaussian sets A, recovering the Gaussian isoperimetric inequality through smooth approximations.The argument extends the inequality from sufficiently smooth [0,1]-valued Gaussian functions using a central-limit argument, then approximates 1A.Source: §11.4 · p. 347
• The proof of Bobkov’s inequality reduces the general case to a two-point inequality and uses a discretized Barthe–Maurey argument with a submartingale and optional stopping.The proof allows an additive error Cδτ3, which vanishes as τ becomes arbitrarily small.Source: §11.4 · pp. 347–349
• For f : {−1,1}^n → [0,1], E[∥(U(Tρ f), ∇Tρ f)∥] increases with ρ on [0,1], recovering Bobkov’s Inequality at ρ = 0,1.Source: §11.4 · p. 350
• De, Mossel, and Neeman [DMN13] give a Bobkov-style Boolean inductive proof yielding both Borell’s Isoperimetric Theorem and the Majority Is Stablest Theorem.Source: §11.4 · p. 350

11.5. The Berry–Esseen Theorem

• For independent variables with matching first and second moments, the Replacement Method compares sums on smooth tests by replacing variables one at a time.The Invariance Principle for Sums applies to tests with continuous third derivative; the proof uses moment matching to cancel lower-order Taylor terms.Source: §11.5 · pp. 354–355
• The Variant Berry–Esseen bound is incomparable with the standard version: it gives error .433γ for comparing E[cosS] and E[cosZ], while recovering the standard conclusion costs O(γ^1/4).The passage notes that the cosine comparison cannot be directly deduced from standard Berry–Esseen.Source: §11.5 · p. 356
• Mollification extends the invariance principle to Lipschitz tests: a c-Lipschitz function admits a smooth approximation with uniform error at most cη and controlled derivatives.The derivative bounds depend on η and the derivative order.Source: §11.5 · p. 356
• Smoothing threshold tests and using Gaussian anticoncentration yields a weaker classical Berry–Esseen cdf bound, with a loss of a power of 1/4.The text contrasts this weaker bound with the standard Berry–Esseen rate.Source: §11.5 · p. 357

11.6. The Invariance Principle

• The section begins generalizing replacement-based invariance from linear sums to degree-k multilinear polynomial forms, using independent mean-zero, variance-one inputs with bounded third absolute moments.Source: §11.6 · p. 358
• For low-degree functions with small influences, replacing independent Boolean inputs with Gaussians changes the distribution little, as tested by Lipschitz functions.The basic invariance principle uses moment-matched inputs and applies when the test function is sufficiently smooth; a Lipschitz-test version is also given. Unbiased Boolean-valued functions cannot satisfy both the low-degree and small-influence conditions in this setting.Source: §11.6 · pp. 358, 361, 362
• Noise-stable functions can be handled by truncating to low degree, and smoothing a function with no notable coordinates yields a Boolean-to-Gaussian comparison.The corollary applies when the function has variance at most 1 and its low-degree truncation has small influences; the smoothed version assumes no (ϵ,δ)-notable coordinates.Source: §11.6 · p. 362
• The invariance results also yield Lévy-distance bounds and, using Gaussian polynomial anticoncentration, a cdf-closeness bound for small-influence functions.The stated Lévy bound is O(2^kϵ^1/5) under the preceding corollary’s setting; the cdf result assumes degree at most k, ϵ-small influences, and variance 1.Source: §11.6 · pp. 363–364

11.7. Highlight: Majority Is Stablest Theorem

• Assuming the Majority Is Stablest Theorem, it is Unique Games-hard to approximate Max-Cut better than the Goemans–Williamson algorithm.The conjecture’s original motivation was Max-Cut approximability.Source: §11.7 · p. 364
• Goemans–Williamson uses an SDP solution followed by random Gaussian hyperplane rounding, achieving an expected cut worth at least cGW times the Max-Cut value, where cGW≈.8786.A refined guarantee states that for θ∈[θ*,π], with θ*≈.74π, the algorithm achieves expected cut value at least θ/π when the graph meets the theorem’s SDPOpt condition.Source: §11.7 · pp. 365–366
• A Z5 example attains an optimal integrality gap, showing that the Goemans–Williamson analysis cannot be improved in the stated case.The example concerns the bound relating Opt(G) to SDPOpt(G).Source: §11.7 · p. 366
• UG-hardness yields a Max-Cut approximation ratio α/β≈.8787, close to the Goemans–Williamson constant cGW≈.8786.The passage presents this as a hardness result for approximating Max-Cut.Source: §11.7 · p. 367
• The General-Volume Majority Is Stablest Theorem covers functions into [0,1] with small maximum influence or no notable coordinates, for 0≤ρ<1.Its proof reduces to Borell’s theorem using the Basic Invariance Principle twice, after smoothing the function.Source: §11.7 · p. 368
• Among voting rules with ϵ-small influences, majority rule is the most rational under the passage’s Condorcet-election criterion.The criterion is the probability of having a Condorcet winner, described as a rational outcome.Source: §11.7 · pp. 369–370

11.8. Exercises and notes

• The exercises include problems on Gaussian surface area and boundary definitions, and on the Gaussian quadrant probability function associated with Borell’s theorem.The notes introduce the Gaussian quadrant probability function as a generalization of the function appearing in Borell’s Isoperimetric Theorem.Source: §11.8 · pp. 372–373
• For sets A and B of fixed Gaussian measures, parallel halfspaces attain the maximum joint Gaussian noise stability; taking B = A recovers Borell’s theorem [MN12], while Borell’s original result is more general.The exercises use the two-set theorem as the target of Mossel and Neeman’s proof.Source: §11.8 · p. 375
• The two-function theorem is presented as an intermediate route to the two-set theorem, and its n-dimensional form follows from the two-set theorem in dimension n+1.The reverse implication to the two-set and [0,1]-valued Borell theorems is also posed for proof.Source: §11.8 · p. 375
• The two-function inequality tensorizes from dimension 1 to all dimensions using induction by restrictions, without relying on properties of Λρ beyond the product structure of correlated Gaussians.The exercises also identify equality cases for indicator functions of affine halfspaces and for Gaussian-CDF transforms of affine functions.Source: §11.8 · p. 375
• In the one-dimensional proof, a smoothed Gaussian-stability expression is shown to be nonincreasing, with the argument using ρ-concavity of the Gaussian quadrant probability Λρ for 0 < ρ < 1.The exercises develop the result through a derivative formula involving the ρ-concave function’s Hessian.Source: §11.8 · pp. 376–377
• Dictator functions are a counterexample to the exact 1-bit two-function inequality, while a weakened version with an influence-dependent error is extended by induction to n-bit functions valued in [ϵ, 1 − ϵ].The weakened result is attributed to De, Mossel, and Neeman [DMN13].Source: §11.8 · pp. 377–378
• The exercises establish an optimal SDP integrality gap of 1/2 for a Max-E2-Lin instance.The instance’s constraints form a cycle of four equalities with one sign reversal.Source: §11.8 · p. 379
• Borell’s Isoperimetric Theorem has several proofs, including symmetrization, semigroup, Boolean, and stochastic-calculus approaches [DMN12].Borell’s original proof used Ehrhard symmetrization and yielded stronger results for nonnegative functions.Source: §11.8 · p. 386
• Mossel, O’Donnell, and Oleszkiewicz obtain explicit invariance-principle error bounds by combining replacement with hypercontractivity, unlike Rotar’s less explicit bounds.The notes trace invariance principles from Rotar’s work on low-influence polynomials to later results with more readily stated error bounds.Source: §11.8 · pp. 386–387
• The Majority Is Stablest conjecture was proved by Mossel, O’Donnell, and Oleszkiewicz, and related Max-Cut approximation and hardness results developed around the threshold θ* [GW94, FS02, OW08].Feige and Schechtman established an optimal SDP integrality gap for θ ≥ θ*, while O’Donnell and Wu gave matching approximation, integrality-gap, and UG-hardness results for 1/2 < β < 1.Source: §11.8 · p. 387
• Raghavendra showed that any CSP’s SDP integrality gap yields a matching Dictator-vs.-No-Notables test, implying matching approximation algorithms and UG-hardness results.The notes also identify Austrin as providing precursors to this theory.Source: §11.8 · p. 387

Some tips

• The closing tips recommend testing conjectures on standard Boolean functions, trying induction or Gaussian-space special cases, and looking for reductions to degree-1 polynomials.They suggest applying analysis of Boolean functions to problems involving Boolean strings and product probability spaces.Source: Some tips · p. 389

• Applications and related topics indexed include learning theory, circuit complexity, social choice, CSPs, and approximation algorithms.Entries include constant-depth circuits and learning, Arrow’s and Condorcet topics, Max-CSP, Max-Cut, and Goemans–Williamson.Source: Index · pp. 413, 414, 416, 417
• Fourier entries cover the expansion, coefficients, basis and formula, Parseval’s Theorem, and the Fourier spectrum.The index gives page references for these core topics.Source: Index · pp. 415, 417
• The index also covers Gaussian analysis and extensions to product spaces, including Gaussian noise, Hermite expansions, and product-space Fourier analysis.It lists Gaussian space and surface area, Hermite polynomials, and product-space domains and bases.Source: Index · pp. 415, 417
• Analytic topics include hypercontractivity, influence, noise operators and stability, and invariance principles.The index lists variants of hypercontractivity, several forms of influence, noise stability across spaces, and invariance principles.Source: Index · pp. 415–417

Index

• The index cross-references the Hypercontractivity, Reverse Reverse Small-Set Expansion, and correlated-Gaussian entries, and lists stable influences and Small-Set Expansion pages.It also directs readers from ρ-stable hypercube graph to noisy hypercube graph and from ρ-correlated strings to correlated strings.Source: Index · p. 418
• Entries cover rotation sensitivity, subadditivity, Russo–Margulis, satisfiability, the second moment method, semidefinite programming, semigroup property, Shapley value, and related topics.The index gives page numbers or redirects readers to related entries for these terms.Source: Index · p. 418
• The index lists Siegenthaler’s Theorem, spectral and Fourier concepts, stable influence, degree-1 weight, subcube partition, subspaces, and Switching Lemma entries.Baby and Håstad variants of Switching Lemma have separate page references.Source: Index · p. 418
• The T entries include tensorization as a hypercontractivity cross-reference, test functions, Lipschitz and dictatorship testing, variance, and voting-rule cross-references.The index also points to linearity testing, threshold functions, and CSP value.Source: Index · pp. 418–419
• The W entries list Walsh functions and the Walsh–Hadmard Matrix, direct weight references, and cross-references for weight and weighted majority.Weighted majority points to linear threshold.Source: Index · p. 419