  A natural measure of smoothness of a Boolean function is its sensitivity (the
largest number of Hamming neighbors of a point which differ from it in function
value). The structure of smooth or equivalently low-sensitivity functions is
still a mystery. A well-known conjecture states that every such Boolean
function can be computed by a shallow decision tree. While this conjecture
implies that smooth functions are easy to compute in the simplest computational
model, to date no non-trivial upper bounds were known for such functions in any
computational model, including unrestricted Boolean circuits. Even a bound on
the description length of such functions better than the trivial $2^n$ does not
seem to have been known.
  In this work, we establish the first computational upper bounds on smooth
Boolean functions:
  1) We show that every sensitivity s function is uniquely specified by its
values on a Hamming ball of radius 2s. We use this to show that such functions
can be computed by circuits of size $n^{O(s)}$.
  2) We show that sensitivity s functions satisfy a strong pointwise
noise-stability guarantee for random noise of rate O(1/s). We use this to show
that these functions have formulas of depth O(s log n).
  3) We show that sensitivity s functions can be (locally) self-corrected from
worst-case noise of rate $\exp(-O(s))$.
  All our results are simple, and follow rather directly from (variants of) the
basic fact that that the function value at few points in small neighborhoods of
a given point determine its function value via a majority vote. Our results
confirm various consequences of the conjecture. They may be viewed as providing
a new form of evidence towards its validity, as well as new directions towards
attacking it.
