Consequences of the Sensitivity Theorem #
A direct numerical corollary of sensitivity_ge_sqrt_degree: the
multilinear degree of any Boolean function is bounded above by the square
of its sensitivity.
Main results #
LeanPoolSensitivity.degree_le_sensitivity_sq—f.degree ≤ f.sensitivity^2.
The multilinear degree is at most the square of the sensitivity, an
immediate corollary of the sensitivity theorem √d ≤ s(f): squaring both
sides yields d ≤ s(f)^2.