734aa00
================================================================================
AVERAGE SENSITIVITY OF POLYNOMIAL THRESHOLD FUNCTIONS
a complete self-contained proof
================================================================================
WHAT THIS DOCUMENT IS.
A polynomial threshold function (PTF) reads n yes/no bits and returns a yes/no
answer, by evaluating a real polynomial and looking at the sign. We prove that
if the polynomial has degree at most d, then very few input bits matter on
average: the expected number of bits whose flip changes the answer is at most
8 d sqrt(n).
This is a real theorem with history. Gotsman and Linial conjectured (1994) the
exact maximizer among all degree-d PTFs. That exact conjecture is FALSE (Chapman
2018; Kim-Maldonado-Wellens 2017 for d = 2). But the ASYMPTOTIC statement -- an
O(d sqrt n) bound with an absolute constant -- is TRUE, and this document proves
it in full.
Everything is proved from scratch. Prerequisites: finite sums, linear algebra
over the reals (orthogonal projection, matrix / Hilbert-Schmidt norm), and the
triangle and Cauchy-Schwarz inequalities. That is it.
THE RESULT.
THEOREM (Main). Let n >= 1 and 1 <= d <= n. Let p be a real multilinear
polynomial in x_1,...,x_n of degree at most d, and define
f(x) = sgn(p(x)) on the Boolean cube {-1,+1}^n,
with the convention sgn(0) = +1. Then
I(f) <= 8 d sqrt(n),
where I(f) is the average sensitivity (Section 0.2) under the uniform
probability measure on {-1,+1}^n.
The constant 8 is absolute: it does not depend on d or n. The polynomial may
vanish on the cube. No other condition is assumed.
CONTENTS.
0. The cube, sensitivity, degree: the players
1. The proof in one paragraph (road map)
2. A one-sided coupling lemma
3. The weighted grading of the cube
4. Recovering edges from the anticommutator
5. Parity, the binomial coupling, and the main theorem
6. Two consequences: noise sensitivity and agnostic learning
References
================================================================================
SECTION 0. THE BOOLEAN CUBE, SENSITIVITY, DEGREE: THE PLAYERS
================================================================================
0.1 The cube.
A point of the cube is a vector x = (x_1,...,x_n) with each x_i in {-1,+1}.
There are 2^n points. Read "+1" as "yes" and "-1" as "no"; the cube represents
all 2^n yes/no answer sheets to n questions.
The Hamming distance rho(x,y) is the number of coordinates where x and y differ.
Two points are NEIGHBORS if rho(x,y) = 1. An EDGE is an ordered pair (x,y) of
neighbors; there are n 2^n of them (each of the 2^n points has exactly n
neighbors, and we count both directions).
"Uniform measure" means we pick X uniformly at random from the 2^n points, so
each point has probability 2^{-n}. We write E and Pr for expectation and
probability under this measure.
0.2 Sensitivity.
Fix a function f: {-1,+1}^n -> {-1,+1} such as a PTF. Coordinate i is SENSITIVE
at x if flipping just x_i changes the answer: f(x) != f(x^{ei}), where x^{ei}
is x with coordinate i flipped. The AVERAGE SENSITIVITY (equivalently the total
influence) is
I(f) = sum_{i=1}^{n} Pr{ f(X) != f(X^{ei}) },
with X uniform. In words: pick a random point, then a random coordinate; I(f) is
the probability that flipping that one coordinate changes the answer.
Two views are the same thing:
I(f) = (1 / 2^n) * (number of ordered sensitive edges),
where an ordered edge (x,y) is sensitive if f(x) != f(y). Indeed, each x
contributes exactly its number of sensitive neighbors, and summing over x and
dividing by 2^n gives the expected sensitive-neighbor count on the left. Both
sides equal I(f). We use this identity often.
0.3 Examples that anchor the scale.
DICTATOR. f(x) = x_1. Flipping coordinate 1 always changes the answer; flipping
any other coordinate never does. So I(f) = 1. Degree 1. Compare to the bound
8*1*sqrt(n): fine.
MAJORITY. f(x) = sgn(x_1 + ... + x_n). A random point is "near the boundary"
(sum close to 0) with probability about const / sqrt(n) by the central limit
theorem, and the number of sensitive coordinates at such a point is about
sqrt(n). So I(f) is of order sqrt(n). Degree 1. Compare to 8*1*sqrt(n): tight
up to constants. So the answer cannot be much smaller than sqrt(n) already for
d = 1.
0.4 Polynomial threshold functions; "multilinear".
A PTF is f(x) = sgn(p(x)) for a real polynomial p. On the cube, x_i^2 = 1 for
every i, so any monomial x_1^{a_1}...x_n^{a_n} with some a_i >= 2 can be reduced
by deleting pairs of x_i. Reducing every monomial this way yields a MULTILINEAR
polynomial of degree at most the original and with the SAME values on the cube.
So "degree at most d" for a PTF is well defined: we may assume p is multilinear.
Convention: sgn(t) = +1 if t >= 0, and -1 if t < 0; so sgn(0) = +1.
0.5 The bound is sharp: symmetric examples.
Let 1 <= d <= sqrt(n). Let t(x) be the number of +1 coordinates:
t(x) = (n + x_1 + ... + x_n) / 2.
Let J be the d integers in {0,1,...,n-1} nearest (n-1)/2 (tie broken
arbitrarily), and set
p_J(x) = prod_{j in J} ( t(x) - j - 1/2 ).
This has degree <= d (after multilinearizing). Its sign changes exactly when
t(x) crosses a half-integer j + 1/2 with j in J, i.e. when the point moves
between Hamming-weight levels t = j and t = j+1. Between those two levels there
are n C(n-1, j) ordered edges (choose which endpoint; the standard count). So
I(sgn p_J) = n 2^{-(n-1)} sum_{j in J} C(n-1, j).
Stirling's formula shows C(n-1,j) is comparable to 2^{n-1}/sqrt(n) for j within
sqrt(n)/2 of the center, and all selected j lie there. Each normalized term is
about 1/sqrt(n), and summing over |J| = d terms gives
I(sgn p_J) ~ d sqrt(n) (absolute constants).
Hence the order d sqrt(n) is sharp for 1 <= d <= sqrt(n). (For every Boolean
function I(f) <= n trivially; beyond d ~ sqrt(n) the theorem bound is weaker
than this trivial one, which is fine.)
0.6 Where this sits (short history).
Early works proved sublinear influence for fixed degree: Harsha-Klivans-Meka [5]
got 2^{O(d)} n^{1 - 1/(4d+6)}; Diakonikolas-Raghavendra-Servedio-Tan [3] got
2^{O(d)} (log n) n^{1 - 1/(4d+2)}. Kane [8] reached the sqrt(n) exponent:
I(f) <= sqrt(n) (log n)^{O(d log d)} 2^{O(d^2 log d)},
i.e. n^{1/2 + o(1)} with a polylogarithmic loss for fixed d. The theorem below
removes the loss and gives a clean 8 d sqrt(n). Smaller moments of the local
sensitivity were studied by Chang-Slote-Volberg-Zhang [1] and Tseng-Volberg [11].
The exact extremal conjecture of Gotsman-Linial [4] was disproved by Chapman [2]
and by Kim-Maldonado-Wellens [9]; this document proves only the asymptotic bound.
================================================================================
SECTION 1. THE PROOF IN ONE PARAGRAPH (ROAD MAP)
================================================================================
One probabilistic lemma plus one operator construction, glued by parity.
(a) ONE-SIDED COUPLING LEMMA (Section 2). If two real random variables have the
same distribution, variance sigma^2, and satisfy V - U <= a almost surely,
then E(U - V)^2 <= 8 a sigma. No lower bound on V - U is needed.
(b) WEIGHTED GRADING (Section 3). For any strictly positive weight w we build a
self-adjoint operator M with spectrum fixed by the dimensions of polynomial
degree spaces (eigenvalue k - n/2 on the k-th grade), so
||M||_HS^2 = n 2^n / 4 with no dependence on w. Multiplication by a coordinate
connects only equal or adjacent grades.
(c) EDGES FROM THE ANTICOMMUTATOR (Section 4). For any sign function h, the
equal-sign edges of h are controlled by MH + HM, where H multiplies by h.
(d) PARITY TRICK (Section 5). Given a PTF f = sgn(p), set w = |p| and
h = (full parity) * f. Equal-sign edges of h are exactly the sensitive edges
of f, and the polynomial structure of p forces a one-sided constraint
V - U <= d on a certain binomial coupling.
(e) ASSEMBLE (Section 5, final steps). The one-sided constraint, the fixed energy
of M, and the anticommutator bound give I(f) <= 8 d sqrt(n).
Read in order; each section is self-contained given Section 0.
================================================================================
SECTION 2. A ONE-SIDED COUPLING LEMMA
================================================================================
The core is an elementary estimate about two random variables. If V is never
much bigger than U, and U and V have the same spread, then the typical gap
|U - V| cannot be large. Notice: V may be ARBITRARILY SMALLER than U; only the
upward side is bounded. Equality of the two distributions supplies the
counterweight.
LEMMA 2.1 (coupling). Let U and V be real random variables with the SAME
distribution, finite mean m, and finite variance sigma^2. Suppose
V - U <= a almost surely
for some a >= 0. Then
E(U - V)^2 <= 8 a sigma.
PROOF.
Idea: we want an increasing function g whose gaps reflect gaps of U, V, so
that E|g(V) - g(U)| bounds E(V - U)^2, yet whose gaps we can control using
only the upper bound V - U <= a. Since g is increasing, g(V) - g(U) has the
same sign as V - U; and E[g(V) - g(U)] = 0 because U and V have the same law.
So the expected positive part equals the expected negative part, and the
positive part occurs only where V > U, exactly where the a-bound applies.
Define the anchor
g(t) = integral_{m}^{t} |z - m| dz = (1/2) (t - m) |t - m|.
It is strictly increasing; away from t = m its derivative is |t - m|.
Step A (increment bounds). For real u < v:
(v - u)^2 / 4 <= g(v) - g(u)
<= ((v - u) / 2) ( |u - m| + |v - m| ). (2.2)
Lower bound. g(v) - g(u) = integral_u^v |z - m| dz.
- If u <= m <= v: the integral is (m - u)^2/2 + (v - m)^2/2. Put A = m - u,
B = v - m, both >= 0. Then A^2 + B^2 >= (A+B)^2/2 (equivalent to
(A-B)^2 >= 0), so the integral >= (A+B)^2/4 = (v - u)^2/4.
- If [u,v] lies entirely on one side of m, the integral is at least
(v - u)^2/2 >= (v - u)^2/4.
Upper bound. |z - m| is convex in z, so its graph on [u,v] lies below the chord
joining (u, |u-m|) and (v, |v-m|). Integrating the chord over [u,v] gives
((v-u)/2)(|u-m| + |v-m|).
Step B (integrability; equal means). Applying Step A with |v - u| in place of
v - u (g is increasing, so for v < u swap roles) gives
|g(v) - g(u)| <= (|v - u| / 2)(|u - m| + |v - m|).
With finite variance, g(U) and g(V) are integrable, and since U and V have the
same law, E[g(V)] = E[g(U)]. Let Y = g(V) - g(U); then E[Y] = 0.
Step C (bound the absolute expectation). Let Y_+ = max(Y, 0) and
(-Y)_+ = max(-Y, 0). Since E[Y] = 0, E|Y| = E[Y_+] + E[(-Y)_+] = 2 E[Y_+].
Because g is strictly increasing, Y > 0 exactly when V > U. Hence
E|Y| = 2 E[ 1_{V > U} (g(V) - g(U)) ]
<= 2 E[ 1_{V > U} ((V - U)/2)(|U - m| + |V - m|) ]
<= a E[ |U - m| + |V - m| ]
<= 2 a sigma.
Line 2 uses the upper bound of (2.2); line 3 uses V - U <= a on {V > U}; the
last is Cauchy-Schwarz: E|U - m| <= sqrt(E(U - m)^2) = sigma, likewise for V.
Step D (transfer to the squared gap). The lower bound of (2.2), with the
endpoints in increasing order, gives, pointwise,
(V - U)^2 <= 4 |g(V) - g(U)|.
Take expectations and use Step C:
E(U - V)^2 <= 4 E|Y| <= 8 a sigma. []
Remark. We used only that U and V share the same law and the same finite
variance; independence and exchangeability are NOT assumed. The one-sided
bound V - U <= a points the wrong way relative to the conclusion, so the
distributional symmetry is essential. A relative of this same-law, one-sided
difference-bound device appears in Stein's method (Rollin [10]).
================================================================================
SECTION 3. THE WEIGHTED GRADING OF THE CUBE
================================================================================
We build a single self-adjoint operator M whose Hilbert-Schmidt norm is FIXED
(independent of any weight) while its matrix entries are tuned to the
polynomial. The grading splits the function space into n+1 slices indexed by
degree, of dimensions C(n, k).
3.1 Function space and characters.
Let Omega = {-1,+1}^n and N = 2^n. Work in H = C^Omega, complex functions on
the cube, with the COUNTING inner product (no normalization):
<a, b> = sum_{x in Omega} conj(a(x)) b(x).
The point masses delta_x form an orthonormal basis. Write
B_xy = <delta_x, B delta_y> for operator entries,
||B||_HS^2 = sum_{x,y} |B_xy|^2
for the Hilbert-Schmidt norm squared (basis independent), and ||B||_op for the
operator norm.
For S subset [n] = {1,...,n}, the character is
chi_S(x) = prod_{j in S} x_j (empty product = 1).
Facts:
<chi_S, chi_T> = N if S = T, else 0;
chi_S chi_T = chi_{S xor T} (symmetric difference).
Why: a nonconstant character equals +1 on half the cube and -1 on the other
half (pair vertices differing in a coordinate the character uses), so it sums
to zero; the product rule then gives orthogonality. The N characters form an
orthogonal basis of the N-dimensional H.
3.2 Degree filtration.
V_k = span{ chi_S : |S| <= k }, 0 <= k <= n.
Membership: V_k is "Fourier degree at most k". Product rule: if a in V_r and b
in V_s, then conj(b) a in V_{r+s} (since |S xor T| <= |S| + |T|).
3.3 Weighting degrees.
Fix any strictly positive w: Omega -> (0, infinity) and let D = multiplication
by sqrt(w). Then
<Da, Db> = sum_x w(x) conj(a(x)) b(x),
so D converts the WEIGHTED inner product into the counting one. This lets us
rotate the degree filtration according to w while keeping the orthonormal point
basis (where edges live).
Rotate the filtration and take successive orthogonal increments:
K_k = D V_k, K_{-1} = {0},
E_k = K_k intersect (K_{k-1})^perp, 0 <= k <= n,
and let Pi_k be the orthogonal projection onto E_k. Then
H = E_0 (+) E_1 (+) ... (+) E_n (orthogonal direct sum),
and dim K_k = dim V_k = sum_{j=0}^k C(n, j) (D is invertible), K_n = H, so
dim E_k = C(n, k).
Block Parseval. Decomposing any operator B across the E_k in domain and range
gives
||B||_HS^2 = sum_{r,s = 0}^{n} ||Pi_s B Pi_r||_HS^2. (3.1)
3.4 The grading operator.
L = sum_{k=0}^{n} k Pi_k, M = L - (n/2) Id.
Both are self-adjoint with eigenvalues k and k - n/2 on E_k. Crucial:
||M||_HS^2 = sum_{k=0}^{n} C(n, k) (k - n/2)^2 = n N / 4, (3.2)
because sum_k C(n,k)(k - n/2)^2 = N * Var(Bin(n, 1/2)) = N * n/4, which
depends only on n.
3.5 Coordinate multiplication is tridiagonal.
Let Z_i be multiplication by x_i. Then:
(i) Z_i is a self-adjoint unitary and commutes with D (both act pointwise);
(ii) Z_i raises Fourier degree by at most 1, so Z_i K_r subset K_{r+1}
(using Z_i D = D Z_i and Z_i V_r subset V_{r+1});
(iii) hence Pi_s Z_i Pi_r = 0 whenever |s - r| > 1.
Why (iii): take s > r + 1. Z_i Pi_r lands in K_{r+1} subset K_{s-1}, and E_s is
orthogonal to K_{s-1}, so Pi_s kills it. The case s < r - 1 follows by taking
adjoints.
3.6 Sanity check: the unweighted case w = 1.
Then D = Id, E_k = span{chi_S : |S| = k}, and M chi_S = (|S| - n/2) chi_S. The
cube adjacency is (A f)(x) = sum_{y: rho(x,y)=1} f(y). On characters,
sum_{y: rho(x,y)=1} chi_S(y) = (n - 2|S|) chi_S(x).
Proof of the identity: a neighbor y differs at exactly one coordinate i, and
the factor chi_S(y)/chi_S(x) is -1 if i in S and +1 if i not in S. Summing over
the n choices of i gives -|S| + (n - |S|) = n - 2|S|. So
A chi_S = (n - 2|S|) chi_S = -2(|S| - n/2) chi_S = -2 M chi_S. Hence M = -A/2,
and every off-diagonal neighbor entry satisfies |M_xy| = 1/2, so |M_xy|^2 = 1/4.
With a general positive weight, entries can shrink and other entries can appear;
Section 4 controls the bookkeeping.
================================================================================
SECTION 4. RECOVERING EDGES FROM THE ANTICOMMUTATOR
================================================================================
Fix any positive weight w and the operator M of Section 3. Fix a sign
function h: Omega -> {-1,+1} and let H multiply by h. Consider the
anticommutator
T := M H + H M.
On one hand, T vanishes wherever h(x) + h(y) = 0 (opposite signs) and equals
+-2 M_xy on the diagonal and on equal-sign edges. On the other hand, the grade
structure of M controls the norm of T. Together these count equal-sign edges.
LEMMA 4.1 (edge recovery). With the notation above, let
E_h = { (x,y) in Omega^2 : rho(x,y) = 1, h(x) = h(y) }
be the ordered equal-sign edges. Then
|E_h| <= 2 ||MH + HM||_HS^2. (4.1)
PROOF. There are several steps.
STEP A. Every off-diagonal entry of M has modulus at most 1/2.
Consider the commutator C_i := [L, Z_i] = [M, Z_i] = M Z_i - Z_i M
(subtracting the constant (n/2) Id does not change commutators). In grades,
L = sum_k k Pi_k gives, for each (s,r):
Pi_s C_i Pi_r = (s - r) Pi_s Z_i Pi_r. (4.2)
Claim: ||C_i||_op <= 1. Introduce two unitaries
J = sum_{k} (-1)^k Pi_k, W = sum_{k} i^k Pi_k, i^2 = -1,
and the odd part
O_i = (Z_i - J Z_i J) / 2.
First, ||O_i||_op <= (||Z_i||_op + ||J Z_i J||_op)/2 = 1, since Z_i and
J Z_i J are unitaries.
Second, O_i is exactly the tridiagonal part of Z_i. In the (s,r) block the
factor is (1 - (-1)^{s+r})/2: it is 0 on the diagonal (s + r even) and 1 when
s + r is odd. By (3.5), Pi_s Z_i Pi_r is nonzero only when |s - r| <= 1;
combined with s + r odd, nonzero exactly when |s - r| = 1. (Indeed:
Pi_s J = (-1)^s Pi_s and J Pi_r = (-1)^r Pi_r, so
Pi_s J Z_i J Pi_r = (-1)^{s+r} Pi_s Z_i Pi_r.)
Third, conjugation by W multiplies an (s,r) block by i^{s-r}: W Pi_s = i^s Pi_s
and Pi_r W* = (-i)^r Pi_r, so W(Pi_s Z_i Pi_r)W* = i^{s-r} Pi_s Z_i Pi_r. On the
nonzero blocks i^{s-r} = i (s - r) (check s - r = +1 gives i, s - r = -1 gives
-i). Therefore on those blocks
W O_i W* = i C_i,
and since W is unitary, ||C_i||_op = ||O_i||_op <= 1.
Now translate to point entries. For x, y in Omega,
(C_i delta_y)(x) = (M Z_i delta_y)(x) - (Z_i M delta_y)(x).
Since Z_i delta_y = y_i delta_y and (Z_i f)(x) = x_i f(x),
(C_i)_xy = y_i M_xy - x_i M_xy = (y_i - x_i) M_xy.
If x != y, choose i with x_i != y_i. Then |y_i - x_i| = 2 and
2 |M_xy| = |(C_i)_xy| <= ||C_i||_op <= 1,
so |M_xy| <= 1/2 for all off-diagonal x != y. Consequently every off-diagonal
deficit 1/4 - |M_xy|^2 is nonnegative.
STEP B. Distance-weighted energy is bounded by total energy.
From (4.2) and tridiagonality,
||C_i||_HS^2 = sum_{r,s} (s - r)^2 ||Pi_s Z_i Pi_r||_HS^2
<= sum_{r,s} ||Pi_s Z_i Pi_r||_HS^2
= ||Z_i||_HS^2 = N = 2^n,
because |s - r|^2 <= 1 on nonzero blocks and Z_i is unitary. By the entry
formula in Step A, |(C_i)_xy|^2 = (y_i - x_i)^2 |M_xy|^2, and (y_i - x_i)^2 is
4 when x_i != y_i and 0 otherwise. Summing over x, y and dividing by 4:
sum_{x,y : x_i != y_i} |M_xy|^2 = (1/4) ||C_i||_HS^2.
Summing over i: each ordered pair (x,y) contributes once for each coordinate
where x, y differ, i.e. rho(x,y) times. Therefore
sum_{x,y} rho(x,y) |M_xy|^2 = (1/4) sum_i ||C_i||_HS^2
<= (1/4) n N = n N / 4 = ||M||_HS^2,
where the last equality is (3.2).
STEP C. Energy at distance >= 2 is bounded by diagonal energy.
Set
A_0 = sum_{x} |M_xx|^2 (diagonal energy),
F = sum_{rho(x,y) >= 2} |M_xy|^2 (far energy).
Compare sum rho |M_xy|^2 with sum |M_xy|^2 = ||M||_HS^2:
sum_{x,y} (rho(x,y) - 1) |M_xy|^2
= -A_0 + sum_{rho >= 2} (rho - 1) |M_xy|^2
>= -A_0 + F (since rho - 1 >= 1 when rho >= 2).
By Step B this difference is <= 0, so
F <= A_0. (4.3)
STEP D. Total neighbor deficit bounded by diagonal energy.
There are n N ordered neighbor pairs, so sum_{rho = 1} 1/4 = nN/4. Hence
sum_{rho = 1} (1/4 - |M_xy|^2)
= nN/4 - sum_{rho = 1} |M_xy|^2.
Now sum_{rho = 1} |M_xy|^2 = ||M||_HS^2 - A_0 - F = nN/4 - A_0 - F, so
sum_{rho = 1} (1/4 - |M_xy|^2) = A_0 + F <= 2 A_0. (4.4)
This is the DEFICIT CONTROL: the total deficit from the ideal unweighted value
1/4 across all edges is at most twice the diagonal energy.
STEP E. Count equal-sign edges.
Set
A_h = sum_{(x,y) in E_h} |M_xy|^2.
Each individual deficit is nonnegative, so the deficit summed only over E_h is
at most the full deficit (4.4):
sum_{(x,y) in E_h} (1/4 - |M_xy|^2) <= 2 A_0.
The left side is |E_h|/4 - A_h; rearranged,
|E_h| / 4 <= A_h + 2 A_0 <= 2 (A_h + A_0). (4.5)
Finally compute T = MH + HM directly:
T_xy = h(y) M_xy + h(x) M_xy = (h(x) + h(y)) M_xy.
On the diagonal h(x) + h(x) = +-2, squared factor 4. On E_h, h(x) = h(y), so
factor +-2, squared factor 4. Elsewhere factor 0. Hence
||T||_HS^2 = 4 (A_0 + A_h).
Combine with (4.5):
|E_h| / 4 <= 2 (A_0 + A_h) = ||T||_HS^2 / 2,
i.e. |E_h| <= 2 ||T||_HS^2, which is (4.1). []
================================================================================
SECTION 5. PARITY, THE BINOMIAL COUPLING, AND THE MAIN THEOREM
================================================================================
Now specialize the weight to the polynomial. Parity turns sensitive edges
into equal-sign edges, Lemma 4.1 bounds sensitive edges by the anticommutator
of M with multiplication by the parity-twisted sign, and Lemma 2.1 bounds that
anticommutator norm by d.
PROOF OF THE MAIN THEOREM.
STEP 0. Reduce to a polynomial that never vanishes on the cube.
If p is zero somewhere, our convention sgn(0) = +1 already maps those points
to +1. Perturb p by a small positive constant c:
- If p is negative somewhere, take 0 < c < min{ |p(x)| : p(x) < 0 }. Then
p(x) < 0 stays negative (since p(x) + c < 0), a zero becomes c > 0, and a
positive stays positive.
- If p is nowhere negative, take any c > 0. Zeros become positive and
positives stay positive.
In both cases sgn(p + c) = sgn(p) under our convention, and deg(p + c) = deg p
(c has degree 0 <= d). So we may, and will, assume
p(x) != 0 for all x in Omega.
This makes w = |p| strictly positive.
STEP 1. Set up w, h, q, and count sensitive edges.
Let chi = chi_{[n]} be full parity, and set
w = |p|, h = chi * f, q = chi * p.
Since f = sgn(p) and p != 0 on the cube, f(x) |p(x)| = p(x), so
h(x) w(x) = chi(x) f(x) |p(x)| = chi(x) p(x) = q(x). (5.1)
Parity flips sign across EVERY edge: for neighbors x, y, chi(y) = -chi(x).
Hence
h(x) = h(y) <=> chi(x) f(x) = chi(y) f(y)
<=> f(x) = -f(y) <=> f(x) != f(y).
So the ordered equal-sign edges of h are exactly the ordered sensitive edges
of f. By Section 0.2,
I(f) = |E_h| / N. (5.2)
STEP 2. Fourier support of q.
Multiplication by chi_S sends chi_T to chi_{S xor T}. Since chi = chi_{[n]}
and S xor [n] = [n] \ S (set complement), if
p = sum_{|S| <= d} a_S chi_S,
then
q = chi p = sum_{|S| <= d} a_S chi_{[n] \ S}.
Each index set [n] \ S has size n - |S| >= n - d. Therefore
the Fourier support of q lies in degrees >= n - d. (5.3)
STEP 3. Blocks of H vanish below the line r + s = n - d.
Build the weighted grading of Section 3 from w = |p|, and let H be
multiplication by h. Claim:
Pi_s H Pi_r = 0 whenever r + s < n - d. (5.4)
Proof. Take u = Da in E_r and v = Db in E_s, with a in V_r and b in V_s
(degrees <= r and <= s). Then
<v, H u> = sum_x conj(b(x)) a(x) w(x) h(x)
= sum_x conj(b(x)) a(x) q(x) (by (5.1)).
The function x |-> conj(b(x)) a(x) has Fourier degree at most r + s (Section
3.2 product rule). The function q has Fourier support in degrees >= n - d by
(5.3). Characters of different degrees are orthogonal, so the inner product is
0 whenever r + s < n - d. Since this holds for all u in E_r and v in E_s, the
block Pi_s H Pi_r vanishes. []
STEP 4. The anticommutator on blocks and its energy.
With T = M H + H M, on the (s,r) block (using M Pi_r = (r - n/2) Pi_r and
Pi_s M = (s - n/2) Pi_s):
Pi_s T Pi_r = (s - n/2) Pi_s H Pi_r + (r - n/2) Pi_s H Pi_r
= (r + s - n) Pi_s H Pi_r. (5.5)
So by block Parseval (3.1),
||T||_HS^2 / N = sum_{r,s} (r + s - n)^2 ||Pi_s H Pi_r||_HS^2 / N.
(5.6)
STEP 5. Read (5.6) as a second moment of a binomial coupling.
Define a probability law on pairs (R, S) in {0,...,n}^2 by
Pr{ R = r, S = s } = ||Pi_s H Pi_r||_HS^2 / N. (5.7)
This is a probability distribution:
- nonnegative by construction;
- sums to 1 because sum_{r,s} ||Pi_s H Pi_r||_HS^2 = ||H||_HS^2 =
||Id||_HS^2 = N (H is unitary, block Parseval).
Marginal of R: for fixed r,
sum_s ||Pi_s H Pi_r||_HS^2 = ||H Pi_r||_HS^2
= ||Pi_r||_HS^2 = dim E_r = C(n, r),
using ||H Pi_r||_HS = ||Pi_r||_HS (H unitary) and block Parseval on the
operator H Pi_r. So Pr{R = r} = C(n,r)/N, i.e. R ~ Binomial(n, 1/2).
Likewise S ~ Binomial(n, 1/2). In particular E[R] = E[S] = n/2 and
Var(R) = Var(S) = n/4.
Identity (5.6) now reads
||T||_HS^2 / N = E[ (R + S - n)^2 ]. (5.8)
STEP 6. Reflect to get a one-sided constraint.
Define
U = S, V = n - R.
Because R ~ Bin(n, 1/2), so is n - R (binomial symmetry k <-> n - k); hence U
and V have the SAME law, mean n/2, variance n/4. Also
(U - V)^2 = (S - (n - R))^2 = (R + S - n)^2,
so the right side of (5.8) equals E[(U - V)^2]. Block vanishing (5.4) says the
law (5.7) puts zero mass where r + s < n - d; equivalently R + S >= n - d
almost surely. Therefore
V - U = n - R - S <= d almost surely. (5.9)
Here is a schematic (shade = region forced to carry zero mass).
LEFT: grade blocks Pi_s H Pi_r on the (r,s) grid.
The triangle with r + s < n - d is all zero blocks.
s
n |XX\______ r + s = n (the diagonal R+S=n)
|XXX\
n - d |XXXXX\___ r + s = n - d (below this: blocks vanish)
|XXXXXXX\
0 +----------+-- r
0 n-d n
RIGHT: after reflection U = s, V = n - r, that triangle becomes the
region V - U > d, hence V - U <= d almost surely.
STEP 7. Apply the coupling lemma.
Lemma 2.1 with a = d and sigma = sqrt(Var(U)) = sqrt(n)/2 gives
E[(U - V)^2] <= 8 d * (sqrt(n)/2) = 4 d sqrt(n). (5.10)
Combine (5.8) and (5.10):
||T||_HS^2 / N <= 4 d sqrt(n). (5.11)
STEP 8. Finish.
By Lemma 4.1, |E_h| <= 2 ||T||_HS^2. Divide by N and use (5.2):
I(f) = |E_h|/N <= 2 ||T||_HS^2 / N <= 8 d sqrt(n). (5.12)
This completes the proof of the Main Theorem. []
Remark on the two sides of the argument. Parity converted the sensitivity
count into equal-sign edges of h (Lemma 4.1 input). The polynomial p entered
only through its degree, via the Fourier support of q = chi p, which forced
the one-sided constraint V - U <= d. The grading M is weight-agnostic: it can
only see the fixed energy n/4 and the locality of coordinate multiplication.
That separation of concerns is why the constant is absolute.
================================================================================
SECTION 6. TWO CONSEQUENCES
================================================================================
These two results follow from the main theorem by standard reductions and are
independent of the weighted grading. Included for completeness.
6.1 Boolean noise sensitivity.
Let 0 <= eta <= 1/2. Pick X uniform on Omega, and obtain Y by flipping each
coordinate of X independently with probability eta. The noise sensitivity is
NS_eta(f) = Pr{ f(X) != f(Y) }.
At eta = 0, Y = X; at eta = 1/2, Y is independent of X.
COROLLARY 6.1. Let n >= 1 and d >= 0. If f = sgn(p) with deg p <= d on Omega
and sgn(0) = +1, then for 0 < eta <= 1/2,
NS_eta(f) <= 8 sqrt(2) * d * sqrt(eta).
So NS_eta(f) = O(d sqrt(eta)) with an absolute constant.
PROOF.
Constants (deg 0) have NS = 0, so assume d >= 1. Fix an integer q >= 2. Pick
independent uniform signs a_1,...,a_n in {-1,+1} and independent uniform
buckets b(1),...,b(n) in {1,...,q}. Define on {-1,+1}^q:
g(z) = f( a_1 z_{b(1)}, ..., a_n z_{b(n)} ), z in {-1,+1}^q.
This is a PTF of degree <= min(d, q): substitute and multilinearize (Section
0.4). By the main theorem,
I(g) <= 8 * min(d, q) * sqrt(q) <= 8 d sqrt(q).
Now pick z uniform in {-1,+1}^q and J uniform in {1,...,q}. Set
X_i = a_i z_{b(i)}, Y_i = X_i (-1)^{1[b(i) = J]}.
The signs a_i are independent uniform and independent of (b, J, z), so X is
uniform and independent of the flip vector (which depends only on b, J). Given
(b, J), the indicator 1[b(i) = J] is 1 with probability 1/q independently across
i. Hence (X, Y) has exactly the noise law at rate 1/q. And flipping coordinate
J of z (call it z^{eJ}) turns X into Y, because only coordinates with b(i) = J
change. Therefore, averaging over z, J with (a, b) fixed,
Pr_{z,J}{ g(z) != g(z^{eJ}) } = I(g) / q,
since (1/q) sum_{j=1}^q Pr_z{ g(z) != g(z^{ej}) } = I(g)/q. Finally average
over (a, b):
NS_{1/q}(f) = E_{a,b}[ I(g) ] / q <= 8 d / sqrt(q).
Fourier form. Under the uniform PROBABILITY measure on Omega, expand
f = sum_S fhat(S) chi_S with fhat(S) = E[f(X) chi_S(X)]. It is standard that
NS_eta(f) = (1/2) sum_S (1 - (1 - 2 eta)^{|S|}) fhat(S)^2.
This is nondecreasing in eta on [0, 1/2], because 1 - (1-2eta)^{|S|} increases
in eta. Take q = floor(1/eta), so eta <= 1/q <= 1/2 and q >= 1/(2 eta).
Monotonicity plus the bound:
NS_eta(f) <= NS_{1/q}(f) <= 8 d / sqrt(q) <= 8 d sqrt(2 eta).
This is the constant C = 8 sqrt(2). []
Remark. Kane [7] proved the analogous O(d sqrt(eps)) bound under Gaussian
noise; Corollary 6.1 is the Boolean-cube analogue.
6.2 Agnostic learning with a uniform input marginal.
Setup. Class C_{n,d} = { sgn(p) : deg p <= d } on Omega. Fix any joint
distribution D on Omega x {-1,+1} whose X-marginal is uniform; the labels
Y | X may be arbitrary. Let
OPT = min_{f in C_{n,d}} Pr_{(X,Y) ~ D}{ f(X) != Y }.
An agnostic learner draws independent labeled samples from D and returns a
Boolean h; its true error is Pr_{(X,Y) ~ D}{ h(X) != Y }. The goal: settle
within alpha of OPT.
COROLLARY 6.2. Let n, d >= 1 and 0 < alpha, delta < 1. There is an absolute
constant A and a learner using independent samples from D which, with
probability at least 1 - delta, returns a Boolean h with
Pr{ h(X) != Y } <= OPT + alpha.
Its running time and sample size are polynomial in (n+1)^k, 1/alpha, and
log(1/delta), where
k = min{ n, ceil( A d^2 alpha^{-2} log(4/alpha) ) }.
The labels are unrestricted, and h need not be in C_{n,d}.
PROOF (the essential steps, all standard).
(i) L1 approximation by a low-degree polynomial.
For a noise rate eta in (0, 1/2) and rho = 1 - 2 eta, the noise operator acts
on Fourier coefficients by T_rho f = sum_S rho^{|S|} fhat(S) chi_S. For
Boolean f, T_rho f takes values in [-1, 1] and
|f - T_rho f| = 1 - f * T_rho f pointwise.
Taking expectations and using Corollary 6.1 (with constant 8 sqrt(2), call it
C),
||f - T_rho f||_1 = 2 * NS_eta(f) <= 2 C d sqrt(eta).
(ii) Truncate to degree K.
Choose eta = ( alpha / (8 C d) )^2, so 2 C d sqrt(eta) = alpha/4. Let
K = ceil( log(4/alpha) / (2 eta) ).
Let q be the Fourier truncation of T_rho f to degrees <= min(K, n). If K >= n
then q = T_rho f exactly; otherwise Parseval gives
||T_rho f - q||_1 <= ||T_rho f - q||_2
<= rho^{K+1} <= exp( -2 eta (K+1) )
<= alpha / 4,
using rho^{K+1} = (1 - 2 eta)^{K+1} <= exp(-2 eta (K+1)). Combining with (i):
||f - q||_1 <= alpha/2. (6.3)
Taking A = 32 C^2 makes min(K, n) = k in the statement.
(iii) L1-regression learner.
Use the M = sum_{j=0}^k C(n, j) <= (n+1)^k characters of degree <= k as
features. On a training sample of size m, fit a polynomial P in these features
by minimizing the empirical absolute loss
P = argmin (1/m) sum_{i=1}^m | Y_i - P(X_i) |,
a linear program. Then choose a threshold t in [-1, 1] minimizing the empirical
error of h = sgn(P - t); the best threshold is found by sorting the values
P(X_i).
Correctness. A random threshold t ~ Uniform[-1, 1] gives, on average,
Pr{ sgn(P(X) - t) != Y } = (1/2) |Y - P(X)|
(integration over t). So the minimizing threshold satisfies
err(h) <= (1/2) E|Y - P(X)|.
Replacing true by empirical means, using that P is the empirical minimizer over
features, and (6.3) via the triangle inequality, gives
E_{train}[ err(h) ] <= OPT + alpha/4.
The family { sgn(P - t) } over degree <= k polynomials is a family of
HALFSPACES in the M-dimensional feature space, of VC dimension at most M + 1.
Standard VC uniform convergence then gives, for m polynomial in M and 1/alpha,
E_{train}[ err_D(h) ] <= OPT + 3 alpha / 8.
(iv) From expected to high-probability by repetition.
err_D(h) is nonnegative and bounded by 1, and OPT <= 1, so Markov gives that a
single trial has err_D(h) <= OPT + alpha/2 with probability at least alpha/12.
Repeat independently r = ceil( 12 alpha^{-1} log(2/delta) ) times; with
probability >= 1 - delta/2, at least one candidate has true error
<= OPT + alpha/2. On an independent validation sample of size
ceil( 8 alpha^{-2} log(4 r / delta) ), Hoeffding plus a union bound estimates
all r errors to within alpha/4, except with probability delta/2. Selecting the
candidate with the best held-out score yields true error <= OPT + alpha with
probability >= 1 - delta. This proves Corollary 6.2. []
Remark. The core influence bound is what supplies a low-degree L1 approximant
via noise smoothing; the rest is textbook agnostic regression
(Kalai-Klivans-Mansour-Servedio [6]; see also [3]).
================================================================================
REFERENCES
================================================================================
[1] F. Chang, J. Slote, A. Volberg, H. Zhang.
The Boolean surface area of polynomial threshold functions.
Preprint, 2026. arXiv:2604.08095v2.
[2] B. Chapman.
The Gotsman-Linial conjecture is false.
SODA 2018, 692-699. doi:10.1137/1.9781611975031.45.
Preprint: arXiv:2108.02288v1.
[3] I. Diakonikolas, P. Raghavendra, R. A. Servedio, L.-Y. Tan.
Average sensitivity and noise sensitivity of polynomial threshold functions.
SIAM J. Comput. 43 (2014), no. 1, 231-253. doi:10.1137/110855223.
Preprint: arXiv:0909.5011v2.
[4] C. Gotsman, N. Linial.
Spectral properties of threshold functions. Combinatorica 14 (1994),
no. 1, 35-50. doi:10.1007/BF01305949.
[5] P. Harsha, A. Klivans, R. Meka.
Bounding the sensitivity of polynomial threshold functions.
Theory of Computing 10 (2014), no. 1, 1-26. doi:10.4086/toc.2014.v010a001.
[6] A. T. Kalai, A. R. Klivans, Y. Mansour, R. A. Servedio.
Agnostically learning halfspaces. SIAM J. Comput. 37 (2008), no. 6,
1777-1805. doi:10.1137/060649057.
[7] D. M. Kane.
The Gaussian surface area and noise sensitivity of degree-d polynomial
threshold functions. Computational Complexity 20 (2011), 389-412.
doi:10.1007/s00037-011-0012-6. Preprint: arXiv:0912.2709v1.
[8] D. M. Kane.
The correct exponent for the Gotsman-Linial conjecture.
Computational Complexity 23 (2014), no. 2, 151-175.
doi:10.1007/s00037-014-0086-z. Preprint: arXiv:1210.1283v1.
[9] H. W. Kim, C. Maldonado, J. Wellens.
On graphs and the Gotsman-Linial conjecture for d = 2.
Preprint, 2017. arXiv:1709.06650v1.
[10] A. Rollin.
A note on the exchangeability condition in Stein's method.
Statistics & Probability Letters 78 (2008), no. 13, 1800-1806.
doi:10.1016/j.spl.2008.01.043. Preprint: arXiv:math/0611050v2.
[11] C.-K. Tseng, A. Volberg.
Small moments of the sensitivity of polynomial threshold functions.
Preprint, 2026. arXiv:2606.16004v2.
[12] Y. Xu.
On discrete orthogonal polynomials of several variables. Advances in
Applied Mathematics 33 (2004), 615-632.
doi:10.1016/j.aam.2004.03.002. Preprint: arXiv:math/0401418v2.