Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function.

Let $[n]=\{1,2,\dots,n\}$.

If $i\in[n]$, let $\Bbb 1_i$ be length $n$ vector with all $0$s except $1$ at $i$th position.

If $B\subseteq [n]$, then $\Bbb 1_B$ be the length $n$ vector with $1$s only in positions marked by $B$.

If $i\in[n]$ and $x\in\{0,1\}^n$, let $x^i=x\oplus\Bbb 1_i$ where $\oplus$ is $XOR$ operation.

If $B\subseteq [n]$ and $x\in\{0,1\}^n$, let $x^{B}=x\oplus\Bbb 1_B$ where $\oplus$ is $XOR$ operation.

Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$

Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$

Block Sensitivity of $f$ at input $x$, $BS_x(f)$ is maximum $r$ such that there is a set of disjoint subsets $\{B_i\}_{i=1}^r$($\forall i\neq j$, $B_i\cap B_j=\emptyset$) such that $$\forall j\mbox{, }f(x)\neq f(x^{B_j})$$

Block Sensitivity of $f$ is $$BS(f)=\max_xBS_x(f)$$

Given $f$ in $n$-variables, would it be reasonable to ask the complexity class of deciding $S(f)>c$ and $BS(f)>c$ for a fixed $c>0$? I understand that describing a Boolean function takes $2^n$ bits fully.

Does computing $BS(f)$ also take $O(2^{n+\epsilon})$ time as in answers below?

  • $\begingroup$ Is the length of a 0-1 vector x simply $\ \sum x\ $? Is the length of $\ \mathbb 1_B\ $ simply $\ |B|\ $? $\endgroup$ Jan 26, 2015 at 7:06
  • $\begingroup$ No length of vector $x\in\{0,1\}^n$ is $n$. $\endgroup$
    – Turbo
    Jan 26, 2015 at 7:07
  • 1
    $\begingroup$ Thank you. The length of a word is the number of characters of the word--I guess that's the idea here. $\endgroup$ Jan 26, 2015 at 7:12

2 Answers 2


For fixed $c$ the complexity is polynomial time. In fact, you can calculate $S(f)$ in polynomial time by just going over all inputs and calculating the pointwise sensitivity. This takes $O(n2^n)$ on a RAM machine. Given $c > 0$, there are at most $(2+c)^n = (2^n)^{\log_2 (2+c)}$ ways to choose $c+1$ disjoint subsets, and you can check whether there is a point sensitive to all of them in time $O(2^n)$. In total, this gives an $O((2^n)^{\log_2 (2+c)+1})$ algorithm for determining whether $bs(f) > c$.

This leaves open the question of calculating the block sensitivity of a function $f$.

  • $\begingroup$ Is a matching lower bound a possibility? $\endgroup$
    – Turbo
    Dec 30, 2014 at 7:29
  • 1
    $\begingroup$ No, we don't know how to prove superlinear lower bounds on time. $\endgroup$ Dec 30, 2014 at 7:30

[An alternative answer for $BS(f)$]

There is a paper related to this problem.

Scott Aaronson: Algorithms for Boolean Function Query Properties. SIAM J. Comput. 32(5): 1140-1157 (2003)

The paper gives an $O(N^{\log_2 5} \log N)$ algorithm for computing $BS(f)$ if $f$ is given by a truth table of size $N=2^n$. Thus, even if $c$ is not fixed, deciding $BS(f) > c$ is in P.

  • $\begingroup$ "c is not fixed" -- I mean that c is not a constant. $\endgroup$ Dec 30, 2014 at 16:51
  • $\begingroup$ I do not understand the result. Usually people take c fixed. $\endgroup$
    – Turbo
    Dec 30, 2014 at 18:16
  • $\begingroup$ I totally missed understanding this. So this answer tackles $BS(f)$ (looks superquadratic)? $\endgroup$
    – Turbo
    Jan 25, 2015 at 7:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.