1
$\begingroup$

I am looking at this paper : http://arxiv.org/pdf/1411.3419v1.pdf But somehow I am not being able to fish out a method to calculate this quantity called the "block-sensitivity".

Can someone kindly provide some discussion/examples or such?


  • I am wondering if there is a way to talk of "block sensitivity" of any function of the form $f:\Sigma ^n \rightarrow \{0,1\}$ where $\Sigma$ is a finite set.

IF the above is possible then I guess given any such function one can Booleanize it to give another function $f' : \{0,1\}^{n \vert \vert \Sigma \vert \vert } \rightarrow \{0,1\}$ where $\vert \vert \Sigma \vert \vert$ is the number of bits required to encode $\Sigma$ in binary.

  • Then is it true that I can always calculate the "block-sensitivity" of $f$ say $bs(f)$ and from there get $bs(f')$ as $bs(f) = \frac{1}{\vert \vert \Sigma \vert \vert} bs(f')$ ?

(the typical situation I have is where $\vert \vert \Sigma \vert \vert = poly(n)$ and I hope that this doesn't produce any extra complication!)

$\endgroup$
  • $\begingroup$ What research have you done? There are lots of sources that define block sensitivity. I don't understand what your confusion is -- why can't you just plug straight into the definition? What exactly is your question? What don't you understand? What's the definition of block sensitivity that you've found? Is your question, how can I generalize the definition from a function whose domain is $\{0,1\}^n$ to a function whose domain is $\Sigma^n$? $\endgroup$ – D.W. Jul 29 '15 at 21:00
  • $\begingroup$ Is it possible to plug straight into the definition? That is not clear that is even a tractable calculation! (Infact I had a short conversation today with one of the authors of the linked paper and it didn't seem so!) As far as I can decipher in this paper there is no example of an explicit calculation of $bs(f)$ of any function. I am wondering if there is any example like that? (and yes my sub-question is about extending to other functions whose domain is some arbitrary finite set) $\endgroup$ – user6818 Jul 29 '15 at 22:52
  • 1
    $\begingroup$ Block sensitivity can be calculated in quasipolynomial time $O(n^{\log n})$ using the definition (in terms of the number of variables, the definition implies an $O(O(n)^n)$ algorithm for an input of size $2^n$). Using the Bell number instead of the trivial upper bound on the number of possible partitions doesn't improve this bound. $\endgroup$ – Yuval Filmus Aug 2 '15 at 21:39
  • $\begingroup$ ^I guess you are referring to a brute-force algorithm - right? I am looking for some explicit calculation examples. Looking around the net I saw some very peculiar contrived examples. But a Boolean function can be pretty much any multilinear function on n variables. $\endgroup$ – user6818 Aug 2 '15 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.