Questions tagged [decision-tree]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
89 views

What do Arora and Barak mean by $x|_S$ in their definition of certificate complexity?

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 ...