Abstract
The sensitivity of a Boolean function f:{0,1}^n > {0,1} is the maximal number of neighbors a point in the Boolean hypercube has with different fvalue. 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 lblock sensitivity, bs_l(f), where l 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 subexponential in s(f) (which improves the state of the art upper bounds) or that bs_3(f) >= s(f){3epsilon} 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 > [0,1] and show an analog result to that of Kenyon and Kutin: bs_l(f) = O(s(f))^l. Surprisingly, in this case, the bounds are close to being tight. In particular, we construct a bounded function f:{0,1}^n > [0, 1] with bs(f) n/log(n) and s(f) = O(log(n)), a clear counterexample to the sensitivity conjecture for bounded functions.
Finally, we give a new superquadratic separation between sensitivity and decision tree complexity by constructing Boolean functions with DT(f) >= s(f)^{2.115}. Prior to this work, only quadratic separations, DT(f) = s(f)^2, were known.
BibTeX  Entry
@InProceedings{tal:LIPIcs:2016:6318,
author = {Avishay Tal},
title = {{On the Sensitivity Conjecture}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {38:138:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6318},
URN = {urn:nbn:de:0030drops63184},
doi = {10.4230/LIPIcs.ICALP.2016.38},
annote = {Keywords: sensitivity conjecture, decision tree, block sensitivity}
}
Keywords: 

sensitivity conjecture, decision tree, block sensitivity 
Collection: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) 
Issue Date: 

2016 
Date of publication: 

23.08.2016 