blockSensitivity_le_sensitivity_pow4
Provedsensitivity_theorem
Huang 2019 Theorem 1.5: for every Boolean function f, bs(f) <= 2 * s(f)^4.
Preamble
import Definitions.Def_BoolFunc
import Definitions.Def_sensitivity
import Definitions.Def_blockSensitivity
/-!
# Huang 2019, Theorem 1.5
Quartic bound of block sensitivity by sensitivity: combining Thm 1.4
(`deg ≤ s²`) with Tal's bound (`bs ≤ 2·deg²`) yields `bs ≤ 2·s⁴`.
-/
/-- **Huang 2019, Thm 1.5.** For every Boolean function
`f : {0,1}ⁿ → {0,1}`,
block sensitivity is at most `2 · s(f)⁴`. -/Formal statement
theorem blockSensitivity_le_sensitivity_pow4
{n : ℕ} (f : BoolFunc n) :
blockSensitivity f ≤ 2 * (sensitivity f) ^ 4 := by sorrySource
Huang, Hao. "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture." Annals of Mathematics 190.3 (2019): 949-955.