Noise stability of functions with low influences: invariance and optimality

1.1 Harmonic analysis of boolean functions

• Low-influence Boolean-function analysis matters for hardness of approximation, social choice, combinatorics, geometry, and statistical physics.The paper emphasizes applications where large influences can obscure genuinely n-variable behavior or violate modeling goals.Source: §1.1 · pp. 1–2
• The invariance principle transfers optimization problems between product spaces, including from the discrete cube to Gaussian space.The paper highlights that this direction reverses the usual Gaussian-to-discrete strategy associated with hypercontractivity and isoperimetry.Source: §1.1 · p. 2
• The framework is applied to two previously unconnected conjectures: Majority Is Stablest and It Ain’t Over Till It’s Over.The first is motivated by hardness of approximation, while the second comes from social choice theory.Source: §1.1 · pp. 2–3

1.2 Outline of the paper

• The paper proceeds from an overview to the invariance-principle proof, applications proving both conjectures, and a counterexample to a related conjecture.Minor proofs are placed in appendices.Source: §1.2 · p. 3

1.3 Related work

• The multilinear invariance principle extends Lindeberg-style reasoning beyond linear polynomials, with explicit bounds and a setup contrasted with related results.The paper characterizes Rotar′’s result as more qualitative and Chatterjee’s as requiring low worst-case rather than average-case influences.Source: §1.3 · pp. 3–4

2.1 The invariance principle

• The invariance principle shows that low-influence multilinear polynomials have essentially the same distribution under independent inputs and independent standard Gaussians, with explicit error bounds depending on degree and maximum influence.The theorem assumes normalized independent variables with bounded third moments or finite supports; hypercontractivity supplies the proof conditions. Smoothing removes degree dependence for noise-stability applications, and the techniques also yield Berry–Esseen estimates under Lyapunov-type assumptions.Source: §2.1 · pp. 4–5

2.2 Influences and noise stability in product spaces

• The section generalizes influences and noise stability to arbitrary finite product probability spaces, defines T_ρ and S_ρ, and introduces the new operator V_ρ for the It Ain’t Over Till It’s Over problem.The framework applies to real-valued functions, with proofs stated for [0,1]-valued functions and convertible to the [−1,1] range by f 7→2f −1.Source: §2.2 · pp. 6–7

2.3.1 About the problem

• The motivating applications connect low-influence noise stability to Arrow-type social choice questions and PCP-based hardness results, including Khot’s MAX-2LIN(2) bound and the Majority Is Stablest route to .878-hardness for MAX-CUT.Kalai’s framework expresses rational-outcome probability as 3/4 + (3/4)S1/3(f), while Khot’s analysis uses influence bounds to obtain hardness results.Source: §2.3.1 · pp. 7–8

2.3.2 Consequences of confirming the conjecture

• Confirming the generalized Majority Is Stablest conjecture yields sharp consequences: transitive social choice functions attain at most approximately .9123 rational-outcome probability, MAX-2LIN(2) and MAX-2SAT have (1 −ǫ, 1 −O(ǫ1/2))-hardness, and UGC makes the Goemans-Williamson .878 approximation for MAX-CUT optimal.The theorem applies to functions on discrete product spaces whose coordinate atoms have minimum probability at least α and whose influences are at most τ.Source: §2.3.2 · pp. 8–9

2.4 It Ain’t Over Till It’s Over

• The paper confirms the It Ain’t Over Till It’s Over conjecture for arbitrary finite product spaces with means bounded away from 0 and 1, showing that symmetric threshold functions such as Majority are the worst examples.The result assumes coordinate atoms have minimum probability at least α and sufficiently small influences, with a threshold depending on ρ and the mean.Source: §2.4 · p. 10
• The O(·) term hides a constant depending only on α, 1 −µ, ρ, and 1 −ρ.Source: §2.4 · p. 10

3.1 Setup and notation

• Orthonormal ensembles provide a basis for functions on product spaces, allowing functions to be represented as multilinear polynomials in ensemble variables.The framework includes finite product spaces and can also disregard the underlying spaces by working directly with orthonormal random variables.Source: §3.1 · pp. 10–11
• Influence measures the conditional variance contributed by one ensemble, while the formal noise operator Tρ and related quantities depend only on the polynomial.This lets the paper define influences, variance, and noise stability consistently across ensemble sequences.Source: §3.1 · pp. 11–12
• Low-degree influences isolate each coordinate’s contribution from polynomial terms involving at most d ensembles and are constrained in aggregate by the polynomial variance.The framework connects this notion to functions on finite product spaces and to PCP applications.Source: §3.1 · p. 12

3.2 Hypercontractivity

• Hypercontractivity requires polynomial norms to contract between Lp and Lq after noise scaling, and it is inherited when independent hypercontractive ensemble sequences are combined.The paper records constants for Rademacher, Gaussian, uniform, and general finite-space ensembles.Source: §3.2 · pp. 12–13
• Degree-d multilinear polynomials over a (2, q, η)-hypercontractive sequence satisfy norm bounds that control higher moments.General mean-zero variables with finite q-moments, including variables with bounded third moment, yield explicit hypercontractive parameters.Source: §3.2 · p. 13

Proposition 3.15

• Proposition 3.15 supplies hypercontractivity for mean-zero variables with finite q-moments and for variables multiplied by an independent Bernoulli noise selector.These estimates provide parameters used in the invariance-theorem hypotheses.Source: Proposition 3.15 · pp. 13–14

3.3 Hypotheses for invariance theorems — some families of ensembles

• H1 assumes independent (2, r, η)-hypercontractive ensemble sequences with matching moments below order r, while H2–H4 specialize this framework to bounded-moment, finite-space, and Boolean/Gaussian settings.The restricted hypotheses are obtained as immediate corollaries of H1 with corresponding parameter substitutions.Source: §3.3 · pp. 14–15
• H3 covers arbitrary real-valued functions on finite product spaces, whereas H4 includes multilinear polynomials on the uniform Boolean cube and corresponding Gaussian or uniform variables.In H4 the matching third moments agree because the relevant variables are centered.Source: §3.3 · p. 15

3.4 Basic invariance principle, Cr functional version

• Under H1–H4, bounded-degree multilinear polynomials with variance at most 1 and uniformly low influences have close expectations after applying any sufficiently smooth bounded test function to Q(X) or Q(Y).The result formalizes closeness in distribution under the stated ensemble hypotheses.Source: §3.4 · p. 15
• The proof interpolates coordinate by coordinate between X and Y, replacing one ensemble at a time and summing the resulting expectation differences.Taylor expansion, matching moments, and hypercontractivity bound each replacement error.Source: §3.4 · pp. 16–17

• Theorem 3.19 establishes closeness of Q(X) and Q(Y) in Lévy distance, ordinary distributional distance, L1 distance, and under ζ.ζ measures squared distance to [0, 1].Source: §3.5 · pp. 17–18
• Theorem 3.19 requires bounded degree d, variance at most 1, and uniformly small influences under hypotheses H1–H4.Its error bounds hide constants depending only on r, with a displayed H4 term involving 10dτ.Source: §3.5 · p. 18
• Smoothing Q with T1−γ removes the unavoidable degree dependence in the error bounds and becomes the main tool for applications.The smoothed variables are R=(T1−γQ)(X) and S=(T1−γQ)(Y).Source: §3.5 · p. 18
• The smoothed theorem needs only small low-degree influences Inf≤d_i(Q), rather than small total influences.This feature is stated as essential for PCP applications.Source: §3.5 · p. 18
• Theorem 3.20 also applies directly when the high-degree variance satisfies Var[Q>d] ≤ (1−γ)2d for every d.Source: §3.5 · p. 19

3.6.1 Invariance principle for some C0 and C1 functionals

• 3.6.1 constructs smooth approximations to nonsmooth functionals and applies the basic invariance principle to obtain the first three bounds of Theorem 3.19.The approximations control sup-norm error and rth derivatives before optimizing the smoothing scale.Source: §3.6.1 · p. 19

3.6.2 Closeness in distribution

• 3.6.2 proves distributional closeness by comparing Q(X) and Q(Y) through Gaussian polynomials with low small-ball probabilities.The proof bounds the smoothing error using Corollary 3.23 and the functional comparison using Theorem 3.18.Source: §3.6.2 · pp. 20–21

3.6.3 Invariance principle for smoothed functions

• 3.6.3 proves the smoothed theorem by truncating T1−γQ at degree d and separately controlling its low- and high-degree parts.The high-degree remainder is controlled through its variance decay, while low-degree influences are no larger after smoothing.Source: §3.6.3 · pp. 21–22
• The smoothed proof yields Lévy and ζ bounds under variance decay Var[Q>d] ≤ (1−γ)2d, using Chebyshev’s inequality for the high-degree tail.Source: §3.6.3 · pp. 21–22

• The proof compares E[∆s(Q(X))] and E[∆s(Q(G))] using matched first and second moments and bounded qth moments.A Lindeberg-style interpolation controls the difference by a term proportional to s^-q times the qth moments.Source: §3.7 · p. 22
• Hypercontractivity converts the moment comparison into an explicit bound for smooth functionals of Q(X) and Q(G).Source: §3.7 · p. 22
• Replacing Q by Q+t transfers the smooth-functional comparison to distribution functions, and optimizing over s completes the proof.Source: §3.7 · p. 23

4 Proofs of the conjectures

• The invariance principle lets the authors analyze finite-product noise stability in a convenient space: Gaussian space for Majority Is Stablest and the discrete cube for It Ain’t Over Till It’s Over.Source: §4 · p. 23

4.1 Noise stability in Gaussian space

• Borell’s Gaussian result implies Sρ(f) ≤ Γρ(µ) for every measurable f:[0,1] with mean µ, with halfline indicators attaining the extremal benchmark.For balanced functions, Γρ(1/2)=2π arcsin ρ.Source: §4.1 · pp. 24–25

4.2 Majority Is Stablest

• Theorem 4.4 proves a strengthened Majority Is Stablest statement for finite product spaces under small low-degree influences: Sρ(f) ≤ Γρ(µ)+ε.Source: §4.2 · p. 25

4.3 It Ain’t Over Till It’s Over

• The It Ain’t Over Till It’s Over proof first extends the discrete-cube tail bound to arbitrary finite product spaces using the smoothed invariance principle.The extension assumes atom probabilities are bounded below and low-degree influences are small.Source: §4.3 · p. 27
• A second invariance transfer identifies Vρf with a smoothed polynomial on a new orthonormal ensemble, yielding the required tail comparison.Source: §4.3 · p. 28
• Theorem 4.9 gives the generalized It Ain’t Over Till It’s Over conclusion with K′=log(1/(αρ(1−ρ))) and an ε(ρ,µ) threshold.Source: §4.3 · p. 28

Counterexample

• The conjectures are false: completely symmetric odd functions with small influences can have more Fourier weight on levels 1, 2, and 3 than Majority.The constructed functions depend only on the sum of their inputs.Source: §5 · p. 29

Representation

• The analysis uses Hermite expansions because complete symmetry reduces the Boolean counterexample to a function on one-dimensional Gaussian space.The paper defines the relevant orthonormal Hermite basis and the Majority function in this representation.Source: §5 · p. 29

Gaussian construction

• An odd Gaussian function with a carefully chosen threshold has low-level Hermite weight roughly .75913, exceeding the limiting Majority value 2/π + 1/(3π).The maximum occurs at t = 2.69647.Source: §5 · p. 30

Boolean transfer

• The Gaussian construction yields completely symmetric odd Boolean functions fn with each influence at most O(1/√n) and the same low-level advantage.The Boolean functions are obtained by applying the one-dimensional function to the normalized input sum.Source: §5 · p. 30

Implications

• The result narrows the possible strengthening of Bourgain’s theorem to an asymptotic setting, because the proposed finite-dimensional upper bound fails.The section compares the counterexample with Bourgain’s low-influence upper bound and the associated conjectures.Source: §5 · pp. 29–30

Polynomial estimates

• The appendix proves the omitted propositions by adapting standard hypercontractivity arguments to multilinear polynomials over independent ensembles.The proofs use decompositions by degree and orthogonality of homogeneous components.Source: A Hypercontractivity of sequences of… · pp. 33–34

Necessary conditions

• Any (2, q, η)-hypercontractive random variable must have finite qth moment, mean zero, and η ≤ (q − 1)^(-1/2).These necessary conditions follow from small-parameter Taylor expansions.Source: A Hypercontractivity of sequences of… · p. 34

Symmetrization

• For symmetric random variables, independent-copy symmetrization and a Bernoulli sign reduce norm estimates to hypercontractive inequalities.The argument invokes Jensen’s, Fubini’s, and Minkowski’s inequalities.Source: A Hypercontractivity of sequences of… · p. 34

Weighted variables

• For weighted products VX, the same method controls norms using the bound ∥Y∥q ≤ 2ρ^(1/q)∥X∥q.Here Y is formed from independent copies of (X,V).Source: A Hypercontractivity of sequences of… · p. 35

Finite-space bounds

• If every atom of a finite probability space has probability at least α, then for q = 3 the ratio ∥X∥3/∥X∥2 is at most α^(-1/6).This gives VX a (2, 3, ξ3)-hypercontractive bound with ξ3 = 2^(-3/2)α^(1/6)ρ^(1/6).Source: A Hypercontractivity of sequences of… · p. 35

Fourth moments

• For symmetric X with finite fourth moment, the optimal fourth-order hypercontractive constant is min(3^(-1/2), ∥X∥2/∥X∥4).The appendix also specializes this bound to the Rademacher ensemble.Source: A Hypercontractivity of sequences of… · p. 35

Known formulas

• Sheppard’s formula gives the balanced-case value Γρ(1/2), while prior work determines precise small-mean asymptotics for fixed ρ.The appendix cites Sheppard’s formula and existing calculations for the µ → 0 regime.Source: B Properties of Γρ(µ) · p. 35

Dependence on mean

• For fixed correlation, Γρ(µ) varies continuously with µ, with the difference between means bounded by 2(µ2 − µ1).The proof represents the means through Gaussian quantiles and bounds the intervening probability mass.Source: B Properties of Γρ(µ) · p. 35

Dependence on correlation

• The normalized increment I2 = (Γρ2(µ) − µ^2)/ρ2 is at most µ when 0 < ρ1 < ρ2 < 1.This follows from convexity of Γρ(µ) in ρ.Source: B Properties of Γρ(µ) · pp. 35–36

Derivative control

• The derivative estimates are obtained by expanding the Gaussian indicator in Hermite polynomials and bounding two terms by 2^d I2.The argument uses convexity, the Mean Value Theorem, and bounds on the resulting series.Source: B Properties of Γρ(µ) · p. 36

Quantitative consequence

• For 0 < δ < (1 − ρ)/2, the appendix records a quantitative bound used in the paper’s noise-stability arguments.The bound is stated as Corollary B.5 for all 0 < µ < 1 and 0 < ρ < 1.Source: B Properties of Γρ(µ) · p. 36

Contradiction setup

• The proof assumes that P[Tρf > 1 − δ] is at least ε and selects a subset of that high-noise region having measure ε.This sets up the contradiction argument.Source: C Proof of Theorem 4.5 · p. 36

Auxiliary event

• It introduces h = 1{f ≤ b} with b = 1/2 + µ/2 and uses Markov’s inequality to relate the relevant events.The choice of b depends on the function’s mean parameter µ.Source: C Proof of Theorem 4.5 · p. 36

Hypercontractive bound

• A reverse Bonami–Beckner estimate, also available through Borell’s Gaussian corollary, controls the interaction between the selected set and h.The estimate is expressed using α = log(1/E[h]) / log(1/ε).Source: C Proof of Theorem 4.5 · p. 36

Parameter control

• The assumption ε ≤ 1 − µ ensures α ≤ 1, allowing the exponent in the bound to be controlled by the theorem’s parameters.This parameter restriction is used before combining the inequalities.Source: C Proof of Theorem 4.5 · pp. 36–37

Conclusion

• Combining the derived inequalities yields the contradiction needed to complete the proof of Theorem 4.5.The final step explicitly combines equations (32) and (34).Source: C Proof of Theorem 4.5 · p. 37

Function construction

• The function f_n is constructed as a completely symmetric odd Boolean function using threshold intervals determined by an odd integer u.The definition assigns values according to ranges of |x| and preserves odd symmetry.Source: D Proof of Corollary 5.3 · p. 37

Influence estimate

• The total influence equals the expected number of pivotal bits on a random input, and the proof estimates this quantity for f_n.The supplied passage states that the influence is O(√...).Source: D Proof of Corollary 5.3 · p. 37

Probability calculation

• The proof introduces p(n,s) for the probability that a sum of n independent ±1 variables equals s, extending it to integer sets for the needed calculations.These probabilities support the subsequent coefficient and influence computations.Source: D Proof of Corollary 5.3 · p. 37

Fourier analysis

• Symmetry makes all Fourier coefficients at a fixed level equal, while oddness forces the level-0 and level-2 coefficients to vanish.The common coefficient at level d is denoted c_{f_n}(d).Source: D Proof of Corollary 5.3 · p. 37

Asymptotic conclusion

• Explicit factorial simplification and the asymptotic contribution involving c_{f_n}(3)^2 yield equation (30) from Theorem 5.2 as n tends to infinity.The supplied proof fragment identifies this limiting step as completing the proof.Source: D Proof of Corollary 5.3 · p. 37