Strong Sensitivity Conjecture (`bs(f) ≤ s(f)^2`)
Strong Sensitivity Conjecture, for every Boolean function f : {0,1}^n → {0,1}, bs(f) ≤ s(f)^2.
Mathematical statement
Strong Sensitivity Conjecture,
for every Boolean function f : {0,1}^n → {0,1},
bs(f) ≤ s(f)^2.
We call this the strong sensitivity conjecture because the original sensitivity
conjecture only asked for a polynomial bound in terms of s(f). Huang's
celebrated result (often called the sensitivity theorem) gives a quartic bound,
bs(f) ≤ s(f)^4, thereby settling the original conjecture.
Statement source: Papers statement material
Statement terms: Source-specific
Source-specific terms. Therefore does not assert reuse rights beyond attributed display.
Statement artifacts, not proofs
These records expose exact Lean propositions and statement-only wrappers. Defining a proposition does not supply a proof of it. A placeholder-bearing target also contains no proof. Elaboration checks syntax and types; it does not certify that a formalization perfectly captures every nuance of the informal problem.
Pinned Lean formulation 1
strong_sensitivity_conjecture
theorem strong_sensitivity_conjecture {n : ℕ} (f : (Fin n → Bool) → Bool) : blockSensitivity f ≤ sensitivity f ^ 2 := by sorry- Statement source
- Formal Conjectures
- Lean version
- v4.27.0
- Placeholder
- Present; no proof artifact
- Source evidence
- Pinned source index
- Fidelity review
- Community formulation
References