sensitivity_conjecture
Provedsensitivity_theorem
Sensitivity Conjecture (Nisan-Szegedy 1994, resolved by Huang 2019): there exist constants C, k such that for every n and every Boolean function f : {0,1}^n -> {0,1}, block sensitivity is at most C * s(f)^k.
Preamble
import Definitions.Def_BoolFunc
import Definitions.Def_sensitivity
import Definitions.Def_blockSensitivity
/-!
# Sensitivity Conjecture (Nisan–Szegedy 1994, resolved by Huang 2019)
The existential statement that sensitivity and block sensitivity are
polynomially related over all Boolean functions. Huang 2019 Thm 1.5
provides the explicit witnesses `C = 2, k = 4`.
-/
/-- **Sensitivity Conjecture.** There exist constants `C, k : ℕ` such
that for every `n : ℕ` and every Boolean function
`f : {0,1}ⁿ → {0,1}`,
block sensitivity is bounded by `C · s(f)^k`. -/Formal statement
theorem sensitivity_conjecture :
∃ C k : ℕ, ∀ (n : ℕ) (f : BoolFunc n),
blockSensitivity f ≤ C * (sensitivity f) ^ k := by sorrySource
Huang, Hao. "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture." Annals of Mathematics 190.3 (2019): 949-955.