Degree vs. sensitivity: beating the exponent Open Problem
Sensitivity and polynomial degree are two of the basic complexity measures of a Boolean function. Huang (2019) proved , settling the Sensitivity Conjecture (Annals of Mathematics 190(3)). In the other direction, , and nobody knows whether this quadratic upper bound is tight. The largest known gap comes from one explicit…