What do Arora and Barak mean by $x|_S$ in their definition of certificate complexity?
-
05-11-2019 - |
Question
I am having much trouble understanding the following definition (of certificate complexity - for decision trees) from Arora and Barak's book Computational Complexity: A Modern Approach. Perhaps there is a typo in it:
Definition 12.3 (page 262). Let $f : \{0,1\}^n \to \{0, 1\}$, and $x \in \{0,1\}^n$. A 0-certificate for $x$ is a subset $S \subseteq \{0,1\}^n$, such that $f(x') = 0$ for every $x'$ such that $x'|_S = x|_S$ (where $x|_S$ denotes the substring of $x$ in the coordinates in $S$$)\ldots$
So, given that $S$ is a subset of $\{0,1\}^n$, what on earth does $x|_S$ mean? (Their parenthetical remark is not clear to me.)
Is there in fact a typo in what $S$ is?
I've looked online at a few other authors' definitions of certificate complexity, and it seems to me that $S$ should actually be a subset of $[n] = \{1,2,\ldots,n\}$. Is this correct? If so, then $x|_S$ would make sense.
Finally, I'll note that I have looked online for an errata list, but I could not find anything very comprehensive.
No correct solution