Given a Boolean function f, it is known that the sensitivity of f, denoted s(f), is at least the square root of its degree, denoted deg(f), and that this bound is tight.
The upper bound is less clear. It is known that s(f)≤(deg(f))2, with recent work improving this by a constant <1(≈0.83). There is also an explicit construction with s(f)=(deg(f))log(6)/log(3). Here the exponent is ≈1.63.
The goal of this problem is to find a novel construction that improves on this bound.
Read more here.