# Sensitivity and block sensitivity of specific problem, is there an errata? Arora-Barak exercise 12.4

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.

• 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). Commented Jul 8, 2019 at 9:35
• Here, possibly $x_{i=1}$ should be simply ignored, that is, it should simply read $x_i = 1$. Commented Jul 8, 2019 at 9:36
• 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$.
– 3cnf
Commented Jul 8, 2019 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.
• Thanks, it makes sense now. Also, there should be $s(f) = \Theta (\sqrt{n})$, since $s(f ) = \sqrt{n}$ is clearly incorrect.
• 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}$
• You can fix that by requiring $i$ to be even. At any rate, looking at the literature, people care about the constant. Commented Jul 9, 2019 at 7:00