The sensitivity conjecture is the assertion that the block sensitivity of every Boolean function 
is bounded by a fixed
polynomial in its Boolean
function sensitivity, independently of the number of input variables. Huang (2019,
Theorem 1.5) proved the conjecture by establishing
where 
and 
denote Boolean function sensitivity
and block sensitivity.
See also
Block Sensitivity,
Boolean
Function,
Boolean Function Sensitivity
Explore with Wolfram|Alpha
References
Huang, H. "Induced Subgraphs of Hypercubes and a Proof of the Sensitivity Conjecture." Ann. Math. 190, 949-955, 2019.
https://doi.org/10.4007/annals.2019.190.3.6.
Cite this as:
Weisstein, Eric W. "Sensitivity Conjecture."
From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SensitivityConjecture.html
Subject classifications
