  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)). This is the first improvement
on the folklore bound of s/epsilon. Further, we show that improving the bound
to O(s^c log(1/epsilon)^d)$ for any d < 1 and any c > 0 will imply the
sensitivity conjecture. Thus our result is essentially the best one can hope
for without proving the conjecture.
  We postulate a robust analogue of the sensitivity conjecture: if most inputs
to a Boolean function f have low sensitivity, then most of the Fourier mass of
f is concentrated on small subsets, and present an approach towards proving
this conjecture.
