Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-069 | 25th April 2016 22:05

Degree and Sensitivity: tails of two distributions


Authors: Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson
Publication: 28th April 2016 13:52
Downloads: 1830


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.

ISSN 1433-8092 | Imprint