A superquadratic separation between sensitivity and block sensitivity

Follow-up works

• Robin Kothari (GitHub user robinkothari), New problem suggestion: block sensitivity vs. sensitivity (bigospeedrun/site issue #2, 2026-10-15). Proposes tracking the best exponent α in bs(f) ≥ s(f)^(α−o(1)), taking this paper as the baseline; it says the paper's general bounds with d = 20, M = 9^21 give an exponent of about 2.00647 (the Lean witness d = 9, M = 9^10 gives about 2.000252).
• Robin Kothari and Codex, Separation exponent 83/40 (theorem on Prove2Me) (Prove2Me, 2026-10-19). A Lean-checked statement that bs(f) ≥ s(f)^(2.075−ε) with unbounded sensitivity, using "a seven-level construction with nine nested predicates"; it cites this paper's Lean scope document as a foundation. [AI-generated per source]
• Prove2Me, Block Sensitivity vs. Sensitivity: Reach 2.10 (Lean research mission, accepted submission dated 2026-10-20). A follow-up mission to OpenAI result 132 targeting $\mathrm{bs}(f)\ge s(f)^{2.10-\varepsilon}$ with arbitrarily large sensitivity; its activity panel records an accepted submission and marks the goal proved, while the proposal text still describes an open target.
• yousofy with Codex, Separation exponent at least 2.1308255793978239… (Prove2Me, 2026-10-20). Highest Lean-checked exponent in the Prove2Me campaign at collection time; the page calls it a "New construction" and retains the earlier OpenAI and Kothari/Codex attribution, without describing its relation to this paper's construction. [AI-generated per source]
• Qiuyu Chen (canghaimeng), developed with the Euler system, bound-132: larger sensitivity–block sensitivity separation (GitHub, October 2026). Claims α > 380/187 ≈ 2.0321 by keeping this paper's nested-predicate architecture with a level-dependent schedule and 99 OR copies, certified by exact integer inequalities; no Lean proof. [AI-generated per source]
• Codex Block Certificate Audit (agent of @1337isnot1337), audit of Qiuyu Chen's block-sensitivity certificate (Big-O Speedrun discussion board, 2026-10-19). Reports an arithmetic re-check of the 380/187 certificate built on this paper's recurrences and states: "This is not a Lean proof or independently verified separation." [AI-generated per source]

Comments and discussion

• Philip Weiss, answer to How many of the results released by OpenAI went against the conventional mathematical wisdom? (MathOverflow community-wiki discussion, 2026-10-08). Identifies the superquadratic separation as a counterexample to the proposed quadratic bound and distinguishes it from Huang's quartic upper bound.
• Robin Kothari (@RobinKothari), post on X (2026-10-15). Invites Lean-verified improvements on the paper's exponent of about 2.006, stating "The optimal exponent is between 2 and 4. My guess is 2.5 is achievable."
• Robin Kothari (@RobinKothari), post on X (2026-10-16). Reports that within less than a day the separation exponent moved from 2.006 to 2.05 and asks how much higher it can go.

Formalization

• OpenAI math release, Lean scope notes for family 132 (lean/docs/132.md). States that the formalization covers the quantitative ratio $\mathrm{bs}(f)/s(f)^2\ge 2^d/(4(d+2)^2)$ and a fixed exponent $\alpha>2$ along a sequence with unbounded block sensitivity at zero; the comparator statement is SensitivitySeparation.lean.
• OpenAI, OAI/Combinatorics/Sensitivity/Separation.lean (openai/math, commit adc7f12). States quantitative_separation, unbounded_quadratic_separation and fixed_power_separation in namespace OAI.Paper320.
• Google DeepMind formal-conjectures, StrongSensitivityConjecture.lean (GitHub, accessed 2026-10-21). Defines sensitivity and block sensitivity and states the negation of bs(f) ≤ s(f)², tagged research solved and citing this paper [OAI26] and its Lean proof, while the theorem body in the file is sorry.
• Prove2Me, Block Sensitivity vs. Sensitivity (campaign) (Prove2Me, October 2026). Lean 4 campaign whose "OpenAI Baseline" mission formalizes this paper's exponent (≥ 2.000252407, 2026-10-15) and then records Lean-checked improvements, reaching ≥ 2.1308 by 2026-10-20.

Related prior literature mentioned by others

• Pooya Hatami, Raghav Kulkarni, Denis Pankratov, Variations on the Sensitivity Conjecture (arXiv:1011.0354, 2010). Cited in the formal-conjectures file (Question 3.1) as a source of the quadratic bs ≤ s² question that this paper answers in the negative.
• Siddhesh Chaubal and Anna Gal, New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity (ECCC TR18-205, 2018-12-03). Pointed to in Weiss's MathOverflow answer for the history of the quadratic-bound question; gives quadratic separations via more general compositions and algebraic constructions.

Possibly relevant literature (found by the agent, not checked)

• Shalev Ben-David, Pooya Hatami, Avishay Tal, Low-Sensitivity Functions from Unambiguous Certificates (arXiv:1605.07084, 2016/2017). Shows that unambiguous-certificate techniques cannot give a super-quadratic bs vs s separation, relevant to how this paper's construction gets past the quadratic barrier.
• Avishay Tal, On the Sensitivity Conjecture (ICALP 2016, LIPIcs 55). Gives a super-quadratic separation between sensitivity and decision-tree complexity and studies ℓ-block sensitivity; background for the paper's superquadratic bs vs s claim and its composition-based amplification.

Digests and expositions

• Open Mathematics Courses / Claude Opus 5.5, Sensitivity and block sensitivity (undated course, accessed 2026-10-21). Three lessons develop composition and OR lemmas, nested predicates on labelled tournaments, and the sensitivity recurrences leading to the paper's superquadratic separation, with exercises and solutions. [AI-generated per source]
• Orply / Perplexity, Boolean Functions Break Every Quadratic Bound on Block Sensitivity (Orply, 2026-10-11). Explains the paper's nested predicates, gate-repair counting, block multiplication and composition amplification, explicitly leaving the label-existence calculation and full recurrence algebra undeveloped. [AI-generated per source]