ECCC-Report TR16-069https://eccc.weizmann.ac.il/report/2016/069Comments and Revisions published for TR16-069en-usThu, 28 Apr 2016 13:52:58 +0300
Paper TR16-069
| Degree and Sensitivity: tails of two distributions |
Parikshit Gopalan,
Rocco Servedio,
Avishay Tal,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2016/069The 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.
Thu, 28 Apr 2016 13:52:58 +0300https://eccc.weizmann.ac.il/report/2016/069