← All problems

Sensitivity conjecture

34 years old · traced to

In computational complexity, the sensitivity theorem, proved by Hao Huang in 2019, states that the sensitivity of a Boolean function f ⁣:{0,1}n→{0,1}f\colon \{0,1\}^{n}\to \{0,1\} 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

Source: Wikipedia

Progress summary

Refreshed
Open · progress reported

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 s(f)≥deg⁡(f)s(f)\geq\sqrt{\deg(f)} 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 QnQ_n with more than 2n−12^{n-1} vertices has a vertex of degree at least n\sqrt{n}, yielding s(f)≥deg⁡(f)s(f)\geq\sqrt{\deg(f)}.
  • 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.

Sources

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 solutionHide full solution