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

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top