TR-2001-22
Sensitivity, block sensitivity, and l-block sensitivity of boolean functions
Claire Kenyon; Samuel Kutin. 27 April, 2001.
Communicated by Laszlo Babai.
Abstract
Sensitivity is one of the simplest, and block sensitivity one of the most useful, invariants of a boolean function. Nisan and Nisan and Szegedy have shown that block sensitivity is polynomially related to a number of measures of boolean function complexity. The main open question is whether or not a polynomial relationship exists between sensitivity and block sensitivity. We define the intermediate notion of $ell$-block sensitivity, and show that, for any fixed $ell$, this new quantity is polynomially related to sensitivity. We then achieve an improved (though still exponential) upper bound on block sensitivity in terms of sensitivity. As a corollary, we also prove that sensitivity and block sensitivity are polynomially related when the block sensitivity is $Omega(n)$.
Original Document
The original document is available in Postscript (uploaded 8 June, 2001 by
Dustin Mitchell).
