5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is the length of a 0-1 vector x simply $\ \sum x\ $? Is the length of $\ \mathbb 1_B\ $ simply $\ |B|\ $? $\endgroup$ – Włodzimierz Holsztyński Jan 26 '15 at 7:06
  • $\begingroup$ No length of vector $x\in\{0,1\}^n$ is $n$. $\endgroup$ – T.... Jan 26 '15 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$ – Włodzimierz Holsztyński Jan 26 '15 at 7:12
7
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ "c is not fixed" -- I mean that c is not a constant. $\endgroup$ – Hiroki Morizumi Dec 30 '14 at 16:51
  • $\begingroup$ I do not understand the result. Usually people take c fixed. $\endgroup$ – T.... Dec 30 '14 at 18:16
  • $\begingroup$ I totally missed understanding this. So this answer tackles $BS(f)$ (looks superquadratic)? $\endgroup$ – T.... Jan 25 '15 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.