Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-062 | 18th April 2016 19:19

On The Sensitivity Conjecture


Authors: Avishay Tal
Publication: 18th April 2016 21:20
Downloads: 4328


The sensitivity of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ is the maximal number of neighbors a point in the Boolean hypercube has with different $f$-value. Roughly speaking, the block sensitivity allows to flip a set of bits (called a block) rather than just one bit, in order to change the value of $f$. The sensitivity conjecture, posed by Nisan and Szegedy (CC, 1994), states that the block sensitivity, $bs(f)$, is at most polynomial in the sensitivity, $s(f)$, for any Boolean function $f$. A positive answer to the conjecture will have many consequences, as the block sensitivity is polynomially related to many other complexity measures such as the certificate complexity, the decision tree complexity and the degree. The conjecture is far from being understood, as there is an exponential gap between the known upper and lower bounds relating $bs(f)$ and $s(f)$.

We continue a line of work started by Kenyon and Kutin (Inf. Comput., 2004), studying the $\ell$-block sensitivity, $bs_\ell(f)$, where $\ell$ bounds the size of sensitive blocks. While for $bs_{2}(f)$ the picture is well understood with almost matching upper and lower bounds, for $bs_3(f)$ it is not. We show that any development in understanding $bs_3(f)$ in terms of $s(f)$ will have great implications on the original question. Namely, we show that either $bs(f)$ is at most sub-exponential in $s(f)$ (which improves the state of the art upper bounds) or that $bs_3(f) \ge s(f)^{3-\varepsilon}$ for some Boolean functions (which improves the state of the art separations).

We generalize the question of $bs(f)$ versus $s(f)$ to bounded functions $f:\{0,1\}^n \to [0,1]$ and show an analog result to that of Kenyon and Kutin: $bs_{\ell}(f) = O(s(f))^{\ell}$. Surprisingly, in this case, the bounds are close to being tight. In particular, we construct a bounded function $f:\{0,1\}^n \to [0,1]$ with $bs(f) \ge n/\log n$ and $s(f) = O(\log n)$, a clear counterexample to the sensitivity conjecture for bounded functions.

Finally, we give a new super-quadratic separation between sensitivity and decision tree complexity by constructing Boolean functions with $\mathrm{DT}(f) \ge s(f)^{2.115}$. Prior to this work, only quadratic separations, $\mathrm{DT}(f) = s(f)^2$, were known.

ISSN 1433-8092 | Imprint