Sensitivity conjecture
In computational complexity, the sensitivity theorem, proved by Hao Huang in 2019, states that the sensitivity of a Boolean function is at least the square root of its degree, thus settling a conjecture posed by Nisan and Szegedy in 1992. The proof is notably succinct, given that prior progress had been limited.
References
Status
- Solved: Hao Huang. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture (Annals of Mathematics, 2019) https://annals.math.princeton.edu/2019/190-3/p06
Source: Wikipedia
Progress summary
Hao Huang’s short proof settled the sensitivity conjecture in 2019,.
The conjecture, posed by Nisan and Szegedy in 1992, asked whether sensitivity and polynomial degree of every Boolean function are polynomially related. Huang proved the sharp basic inequality via an induced-subgraph theorem for the hypercube.
Known results
- Chung, Füredi, Graham, and Seymour (1988): logarithmic lower bound for large induced subgraphs of the hypercube.
- Gotsman and Linial (1992): reduced the Boolean-function conjecture to the hypercube induced-subgraph problem.
- Huang (2019): every induced subgraph of with more than vertices has a vertex of degree at least , yielding .
- Ambainis and Sun (2017): the best known separation between block sensitivity and sensitivity was quadratic, leaving improvement of Huang’s resulting quartic relation open.
February 2026 formal verification
This independently supports the 2019 resolution; the stronger question of improving the quantitative exponent remains open.
Current status (as of August 2026): Huang’s sensitivity conjecture theorem is settled and has a reported formal verification, while improving the resulting quartic relationship toward the known quadratic lower bound remains open.
Solutions 1
Claimed by OpenAI. The manuscript claims nonconstant total Boolean functions with unbounded block sensitivity and bs(f) >= s(f)^alpha for a fixed alpha > 2. This supplies claimed counterexamples to the quadratic bound of block sensitivity by sensitivity squared. It is related sharpness work on sensitivity; it does not contradict or reprove this page’s established inequality that sensitivity is at least the square root of polynomial degree.See full solution
GitHub repository: https://github.com/openai/math
- OpenAI-132-01-A-superquadratic-separation-between-sensitivity-and-block-sensitivity.pdfOpen