1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

It is a typo. $S$ indeed should be a subset of $[n] = \{1,2,\ldots,n\}$. On page 263, in the second sentence of their proof of Theorem 12.5, they list a 0-certificate (or 1-certificate) as a subset of $[n]$.

Because $S \subseteq [n]$, it is easy to understand $x|_S$ (as is stated in the question). This is just the usual notation for the restriction of a function on a subset of its domain. Note that an $x \in \{0,1\}^n$ can be thought of as a function from $[n]$ to $\{0,1\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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