<p>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 &gt; 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) &gt; c$.</p>

<p>This leaves open the question of calculating the block sensitivity of a function $f$.</p>

CC BY-SA 3.0
2014-12-30T07:29:30.503Z
Is a matching lower bound a possibility?
Turbo
CC BY-SA 3.0
2014-12-30T07:30:52.907Z
No, we don't know how to prove superlinear lower bounds on time.
Yuval Filmus
CC BY-SA 3.0
2014-12-30T07:18:47.577Z
2014-12-30T07:18:47.577Z
Yuval Filmus
<p><strong>[An alternative answer for $BS(f)$]</strong></p>

<p>There is a paper related to this problem.</p>

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

<p>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) &gt; c$
is in <strong>P</strong>.</p>

CC BY-SA 3.0
2014-12-30T16:51:09.150Z
"c is not fixed" -- I mean that c is not a constant.
Hiroki Morizumi
CC BY-SA 3.0
2014-12-30T18:16:41.527Z
I do not understand the result. Usually people take c fixed.
Turbo
CC BY-SA 3.0
2015-01-25T07:43:36.113Z
I totally missed understanding this. So this answer tackles $BS(f)$ (looks superquadratic)?
Turbo
CC BY-SA 3.0
2014-12-30T08:24:34.677Z
2014-12-30T08:24:34.677Z
Hiroki Morizumi
<p>Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function.</p>

<p>Let $[n]=\{1,2,\dots,n\}$.</p>

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

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

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

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

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

<p>Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$</p>

<p>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})$$</p>

<p>Block Sensitivity of $f$ is $$BS(f)=\max_xBS_x(f)$$</p>

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

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

CC BY-SA 3.0
2015-01-26T07:06:15.353Z
Is the length of a 0-1 vector x simply $\ \sum x\ $? Is the length of $\ \mathbb 1_B\ $ simply $\ |B|\ $?
Włodzimierz Holsztyński
CC BY-SA 3.0
2015-01-26T07:07:33.217Z
No length of vector $x\in\{0,1\}^n$ is $n$.
Turbo
CC BY-SA 3.0
2015-01-26T07:12:09.517Z
Thank you. The length of a word is the number of characters of the word--I guess that's the idea here.
Włodzimierz Holsztyński
<cc.complexity-theory><boolean-functions>
Complexity class of sensitivity
Turbo
# Complexity class of sensitivity

(Asked by: username_0 on 2014-12-30)

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?

**Tags:** cc.complexity-theory, boolean-functions

> **Comments:**
> **username_1**: Is the length of a 0-1 vector x simply $\ \sum x\ $? Is the length of $\ \mathbb 1_B\ $ simply $\ |B|\ $?  
> **username_0**: No length of vector $x\in\{0,1\}^n$ is $n$.  
> **username_1**: Thank you. The length of a word is the number of characters of the word--I guess that's the idea here.  

---

## 2 answers

### Answer by username_2 on 2014-12-30. Score: 7 | Accepted answer

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$.

> **Comments:**
> **username_0**: Is a matching lower bound a possibility?  
> **username_2**: No, we don't know how to prove superlinear lower bounds on time.  

---

### Answer by username_3 on 2014-12-30. Score: 9

**[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**.

> **Comments:**
> **username_3**: "c is not fixed" -- I mean that c is not a constant.  
> **username_0**: I do not understand the result. Usually people take c fixed.  
> **username_0**: I totally missed understanding this. So this answer tackles $BS(f)$ (looks superquadratic)?  

---

