How far apart can the two sensitivities be?

Sensitivity and block sensitivity measure two ways that a Boolean function can react to changes in its input. Both are basic measures in query complexity, where the input is accessed one coordinate at a time. Their relationship asks how much a function's response to changes involving several coordinates can exceed its response to individual coordinate changes.

Hao Huang's proof of the Sensitivity Conjecture established a polynomial relationship between sensitivity and polynomial degree in 2019, resolving the qualitative polynomial-relation question. The quantitative problem of obtaining the largest possible separation exponent remains the focus of this campaign. This mission asks for the specific exponent $2.10=21/10$.

The relevant progression is:

• The classical benchmark is a quadratic separation, included among the campaign's proved entries.
• In 2026, OpenAI problem 132 supplied a superquadratic construction and a Lean formalization establishing an exponent strictly above $2$.
• On 16 October 2026, the campaign had accepted proofs at exponents $2.0391$ and $2.05$. The 2.05 entry is the proved benchmark when this proposal is drafted.
• The present mission proposes $2.10$ as the next research target. It does not assert that a construction achieving this exponent is already known.

Boolean functions and sensitive changes

A total Boolean function assigns an output bit to every input consisting of $n$ bits:

$$f:\{0,1\}^n\longrightarrow\{0,1\}.$$

For an input $x$ and a coordinate set $B$, write $x^B$ for the input obtained by flipping exactly the coordinates in $B$. The sensitivity at an input counts the individual coordinates whose flip changes the output:

$$s(f,x)=\bigl|\{i:f(x^{\{i\}})\ne f(x)\}\bigr|.$$

The block sensitivity at an input is the largest number of pairwise disjoint nonempty coordinate sets whose separate flips each change the output:

$$bs(f,x)=\max\bigl\{m:\text{there are disjoint nonempty }B_1,\ldots,B_m \text{ with }f(x^{B_j})\ne f(x)\text{ for all }j\bigr\}.$$

The two global measures maximize over all inputs:

$$s(f)=\max_x s(f,x),\qquad bs(f)=\max_x bs(f,x).$$

There is no restriction to monotone functions, symmetric functions, or any particular construction. The number of variables may vary with the desired sensitivity threshold and approximation to the exponent.

Target: separation exponent at least 2.10

Prove that for every real $\varepsilon>0$ and every integer $S\ge2$, there are a dimension $n$ and a total Boolean function $f$ such that

$$s(f)\ge S,\qquad bs(f)\ge s(f)^{21/10-\varepsilon}.$$

The shared campaign predicate SensitivityCampaign.AchievesExponent (2.10 : ℝ) expresses exactly this statement. The decimal denotes the exact rational number $21/10$. The witnesses may depend on both $\varepsilon$ and $S$; no fixed function is required to work for every threshold. The unbounded-threshold requirement is essential to the asymptotic separation being asked for.

What reaching 2.10 would establish

A solution would strengthen the campaign's proved lower bound on the possible separation exponent from $2.05$ to $2.10$. It would provide Boolean functions with arbitrarily large sensitivity and block sensitivity growing with the specified larger power, with an arbitrarily small loss in the exponent.

This is an open research target, rather than a request to transcribe an existing proof of $2.10$. A complete contribution must establish the mathematical claim and provide a Lean proof using the shared definitions. Improvements to constructions, sharper bounds for existing constructions, and reusable supporting results are all relevant contributions. Acceptance of a proposal merely opens the target; a proof is needed to establish the new bound.

The main difficulty

A successful construction must support many disjoint sensitive blocks while controlling sensitivity at every input. A large collection of block witnesses at one input supplies only part of the required information: the upper bound on sensitivity is global. Bounds that lose too much in this global analysis can erase the desired exponent improvement.

The available campaign infrastructure already includes proved theorems converting suitable finite certificates into the asymptotic conclusion. The unresolved work is to obtain stronger certified bounds on a construction, or to establish the asymptotic target directly. A numerical estimate of a separation exponent does not replace a proof of the inequalities on which that estimate depends.

Formalization scope and existing foundations

Functions are represented as (Fin n → Bool) → Bool. Both complexity measures are natural-number maxima over finite sets; the comparison involving an exponent casts them to real numbers and uses real exponentiation. Since every requested witness satisfies $s(f)\ge S\ge2$, its power has a positive base. Zero-dimensional and constant functions cannot satisfy the sensitivity requirement.

The proposal retains the foundation definitions SensitivitySeparation and SensitivityCampaign. It also references two already-proved supporting theorems, rather than introducing alternative definitions or assuming any particular family of functions:

• SensitivityCampaign.finite_certificate: bounds on sensitivity and block sensitivity at a chosen input, together with an exact power inequality, imply the campaign conclusion at the stated nonnegative exponent.
• SensitivityCampaign.finite_certificate_log: the same finite bounds certify the exponent given by the ratio of their logarithms.

These statements are included as reusable foundation milestones. Their hypotheses require integer bounds greater than one, so the logarithmic denominator is positive. Solvers may use either criterion or prove the quantified target directly. The environment is Lean 4.33.1 with the campaign's pinned Mathlib revision.

Selected references

• Hao Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Annals of Mathematics 190 (2019), 949–955. Article.
• OpenAI, A superquadratic separation between sensitivity and block sensitivity, problem 132, 2026. Formalization scope and source links.
• Prove2Me, Block Sensitivity vs. Sensitivity, 2026. Campaign, shared foundations, and verified entries.