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. We call this the strong sensitivity conjecture because the original sensitivity conjecture only asked for a polynomial bound in terms of s(f).
From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim. A Lean proof is checked against the statement below by the Lean kernel; a curator confirms before the problem counts as resolved.
Cite
@misc{cairn-paper-strong-sensitivity-conjecture,
title = {Strong Sensitivity Conjecture (bs(f) ≤ s(f)^2)},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/paper-strong-sensitivity-conjecture}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-29}
} Also: CITATION.cff · Atom feed of results
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
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.
This file formalizes the strong sensitivity conjecture, asserting:
For every Boolean function f : {0,1}^n → {0,1}, bs(f) ≤ s(f)^2, where bs(f) denotes block sensitivity and s(f) denotes sensitivity.
Huang's theorem proves a quartic upper bound, bs(f) ≤ s(f)^4, thereby resolving the most widely known form of the sensitivity conjecture.
We now ask whether a stronger upper bound holds. Interestingly, the original paper of Nisan and Szegedy, where the sensitivity conjecture first appeared, already speculated that a quadratic upper bound might be the correct relation. On the lower bound side, Rubinstein (https://link.springer.com/article/10.1007/BF01200762) constructed Boolean functions exhibiting the first quadratic separation. The best currently known gap, due to Ambainis and Sun (https://arxiv.org/abs/1108.3494), is bs(f) ≥ (2/3)⋅s(f)^2.
Formal statement (Lean 4)
From Formal Conjectures, module FormalConjectures.Paper.StrongSensitivityConjecture.
theorem strong_sensitivity_conjecture {n : ℕ} (f : (Fin n → Bool) → Bool) :
blockSensitivity f ≤ sensitivity f ^ 2What counts as progress
- A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
- Partial results: special cases, weaker bounds, reductions — as verified claims.
- Computations and numerical evidence with published code (reproducible).
- Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
- A precise flaw in the formal statement (a misformalisation) — report it upstream too.
References
- Induced Subgraphs of Hypercubes and a Proof of the Sensitivity Conjecture by Hao Huang (see Section 3, Concluding Remarks)
- Variations on the Sensitivity Conjecture by Pooya Hatami, Raghav Kulkarni, and Denis Pankratov (see Question 3.1)
- On the Degree of Boolean Functions as Real Polynomials by Noam Nisan, and Mario Szegedy (see Section 4, Open Problems)
Source and licence
Imported from Formal Conjectures (research papers), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.