1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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
    Commented Jul 8, 2019 at 9:35
  • $\begingroup$ Here, possibly $x_{i=1}$ should be simply ignored, that is, it should simply read $x_i = 1$. $\endgroup$
    – dkaeae
    Commented Jul 8, 2019 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$
    – 3cnf
    Commented Jul 8, 2019 at 16:43

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, it makes sense now. Also, there should be $s(f) = \Theta (\sqrt{n})$, since $s(f ) = \sqrt{n}$ is clearly incorrect. $\endgroup$
    – 3cnf
    Commented Jul 9, 2019 at 6:40
  • $\begingroup$ I’m not so sure it’s incorrect. $\endgroup$
    – Yuval Filmus
    Commented Jul 9, 2019 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$
    – 3cnf
    Commented Jul 9, 2019 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
    Commented Jul 9, 2019 at 7:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.