Degree and Sensitivity: tails of two distributions

Understand

The sensitivity of a Boolean function f is the maximum over all inputs x, of the number of sensitive coordinates of x.

• The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-s Boolean function can be computed by a polynomial over the reals of degree poly(s).
• The best known upper bounds on degree, however, are exponential rather than polynomial in s.
• Our main result is an approximate version of the conjecture: every Boolean function with sensitivity s can be epsilon-approximated (in L_2) by a polynomial whose degree is O(s log(1/epsilon)).