The sensitivity of a Boolean function $f$ is the maximum, over all inputs $x$, of the number of sensitive coordinates of $x$ (namely the number of Hamming neighbors of $x$ with different $f$-value). 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 $\ell_2$) by a polynomial whose degree is $O(s \cdot \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 \cdot \log(1/\eps)^\gamma)$ for any $\gamma < 1$ will imply the sensitivity conjecture. Thus our result is essentially the best one can hope for without proving the conjecture.
We prove our result via a new ``switching lemma for low-sensitivity functions'' which establishes that a random restriction of a low-sensitivity function is very likely to have low decision tree depth. This is analogous to the well-known switching lemma for $AC_0$ circuits. Our proof analyzes the combinatorial structure of the graph $G_f$ of sensitive edges of a Boolean function $f$. We introduce new parameters of this graph such as tree sensitivity, study their relationship, and use them to show that the graph of a function of full degree must be sufficiently complex, and that random restrictions of low-sensitivity functions are unlikely to yield complex graphs.
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. We prove a lower bound on tree sensitivity in terms of decision tree depth, and show that a polynomial strengthening of this lower bound implies the robust conjecture. We feel that studying the graph $G_f$ is interesting in its own right, and we hope that some of the notions and techniques we introduce in this work will be of use in its further study.
