There's an exercise in Arora-Barak on sensitivity and block sensitivity. The statement of the problem is:

Let $f$ be a function on $n = k^2$ variables that is an OR of $k$ applications of $g: \{0, 1\}^n \rightarrow \{0,1\}$, all $k$ blocks of variables are disjoint. $g(x_1, \ldots, x_k) = 1$ if there exists $i \in [k-1]$ s.t. $x_i = x_{i=1} = 1$ and $x_j = 0$ for all $j \neq i$. Prove that $s(f) = \sqrt{n}, bs(f) = n/2$.

I am confused about $x_{i=1} = 1$. Is there a typo and should it be $x_{i-1} = 1?$ If it is the case, what about $i=1$? Or is it simply $x_1 = 1?$

Another question is whether $g = 1$ iff the condition holds, or if it is only a sufficient condition.

  • 2
    $\begingroup$ The Arora-Barak book has many typos, esp. in the exercises. To the best of my knowledge, unfortunately they don't have an errata page (like, e.g., Goldreich has). $\endgroup$ – dkaeae Jul 8 '19 at 9:35
  • $\begingroup$ Here, possibly $x_{i=1}$ should be simply ignored, that is, it should simply read $x_i = 1$. $\endgroup$ – dkaeae Jul 8 '19 at 9:36
  • $\begingroup$ The statement says that OR of $k$ clauses has sensitivity $k$, which is problematic: consider some assignment $y$ s.t. $g(y) = 0$. Let $x$ be $k$ copies of $y$. $s(f) = k$ implies that $s(g) = 1$ which is hardly believable for any interpretation of the definition of $g$. $\endgroup$ – diplodoc Jul 8 '19 at 16:43

The definition of $g$ should be: $g(x_1,\ldots,x_k) = 1$ if there exists $i \in [k-1]$ such that $x_i=x_{i+1}=1$ and $x_j = 0$ for $j \neq i,i+1$.

As for your question, whether $g=1$ iff the condition holds, or whether it is just a sufficient condition: in mathematics, when we define something, we use the word "if" to mean "iff". Check your favorite textbook, monograph or paper for many examples.

  • $\begingroup$ Thanks, it makes sense now. Also, there should be $s(f) = \Theta (\sqrt{n})$, since $s(f ) = \sqrt{n}$ is clearly incorrect. $\endgroup$ – diplodoc Jul 9 '19 at 6:40
  • $\begingroup$ I’m not so sure it’s incorrect. $\endgroup$ – Yuval Filmus Jul 9 '19 at 6:42
  • $\begingroup$ Suppose that $y = [0, 1, 0, 0, \ldots, 0], y \in \{0, 1\}^k$. Suppose that $x$ is $k$ copies of $y$. Then, $f(x) = 0$. However, by switching first or third bit in any block, we change the value of the function. It means that $s_f(x) \ge 2\sqrt{n}$. I've checked, and it seems that $s(f) = 2\sqrt{n}$ $\endgroup$ – diplodoc Jul 9 '19 at 6:52
  • $\begingroup$ You can fix that by requiring $i$ to be even. At any rate, looking at the literature, people care about the constant. $\endgroup$ – Yuval Filmus Jul 9 '19 at 7:00

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.