# 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). – dkaeae Jul 8 at 9:35
• Here, possibly $x_{i=1}$ should be simply ignored, that is, it should simply read $x_i = 1$. – dkaeae Jul 8 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$. – diplodoc Jul 8 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. – diplodoc Jul 9 at 6:40
• 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}$ – diplodoc Jul 9 at 6:52
• You can fix that by requiring $i$ to be even. At any rate, looking at the literature, people care about the constant. – Yuval Filmus Jul 9 at 7:00