Sensitivity versus block sensitivity
Sensitivity versus block sensitivity concerns how much larger the block sensitivity of a total Boolean function can be than its sensitivity. After Huang's 2019 proof of the sensitivity conjecture, block sensitivity is known to be at most the fourth power of sensitivity, and the best separations had been quadratic. A manuscript dated 25 September 2026 in OpenAI's public mathematics collection (github.com/openai/math) claims that no quadratic bound holds, and gives a separation by a fixed power larger than two. This page summarizes the published claims and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.
Background
- As recounted in the introduction of the manuscript:
- Nisan introduced block sensitivity and recorded Rubinstein's quadratic separation; Nisan and Szegedy suggested the inequality bs(f) ≤ s(f)2.
- Virza improved the separation to bs(f) = s(f)2/2 + s(f)/2, and Ambainis and Sun obtained bs(f) = (2/3)s(f)2 − s(f)/3.
- Huang's degree bound, with Tal's comparison between degree and block sensitivity, gives bs(f) ≤ s(f)4 for every total Boolean function; Wellens improved the constant to bs(f) ≤ √(2/3) s(f)4 + 1.
- Ambainis and Prūsis observed that a seed function with bs(f,0) > s(f)2 would yield a superquadratic power separation by iteration.
The original results
- Unbounded ratio (25 September 2026). Theorem 1.1 of the manuscript states that for every integer d ≥ 1 there is a nonconstant total Boolean function f with bs(f)/s(f)2 ≥ 2d/(4(d + 2)2), so no inequality bs(f) ≤ C s(f)2 holds for all total Boolean functions.
- Fixed power. Corollary "power-separation" states that there are a real number α > 2 and nonconstant total Boolean functions Fm with bs(Fm,0) ≥ s(Fm)α for every m and bs(Fm,0) tending to infinity. It is obtained by composing a fixed seed function with itself. The manuscript does not state a numerical value of α.
- Method, as described: the construction adapts Meiburg's gated-tournament architecture for spectral sensitivity to nested predicates, with randomly chosen tournament labels that exclude small local configurations, followed by an OR balancing step and composition. The manuscript reports that Meiburg credits GPT-5.6-Sol with the gated-tournament ideas.
- Sources. Commit
1581d4cof the openai/math repository, folder A superquadratic separation between sensitivity and block sensitivity. - Formalization. The collection's scope note states that the formalization disproves a universal quadratic bound and also gives a fixed exponent α > 2. Its Comparator challenge
SensitivitySeparationstates the unbounded-ratio theorem; the fixed-exponent theorem is in the collection's Lean library and is not stated in a challenge.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 17 October 2026) |
|---|---|---|---|---|
| 2026-10-09 | ProveIt project, sensitivity versus block sensitivity (GitHub repository VladimirReshetnikov/ProveIt, commit eb8dee9) |
Extension (explicit exponent) | Two AI-assisted manuscripts refining the construction. The first gives explicit functions with bs(Fm,0) ≥ (100·2646)m and s(Fm) ≤ (9·2318)m, so that bs ≥ sα with α = 2.0320827… > 65/32. The second, using threshold-resolved profiles, reaches the exponent 3667/1809 ≈ 2.0271. | Repository report; states that the manuscripts are unrefereed and that nothing is formalized. |
| 2026-10-10 | acprk/openai-math-followups, note 04 (GitHub) | Extension (bounds on seeds) | A seed function with bs(f,0) > s(f)2 must have sensitivity at least 4 and at least 31 variables, from Amano's enumeration and a SAT search whose refutations are checked by an independent proof checker. The note computes the exponent guaranteed by the manuscript's displayed parameters as about 2.00025. | Repository note, produced with AI assistance. |
| 2026-10-15 | shjvandekamp/math, sensitivity separation (GitHub, commit bc1a918) |
Extension | A deterministic construction of the tournament labels with succinct evaluation, and a sharper profile analysis that, for one fixed explicit seed, raises the certified exponent from 2.0154112468… to 2.0154115475…. | Repository result with AI review; states that these are not claims of peer review or Lean formalization. |
Notes
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.