Decision tree complexity
For [math]x \in \{-1,1\}^n[/math] we let [math]c(A, x)[/math] be the number of queries that the decision tree A (also called algorithm) asks when the input to f is x. Let [math]c(A) := \max_x c(A, x)[/math] be the maximum number of queries that A makes which we view as the cost of A on f. This is the same as the depth of the decision tree; the maximum distance of a leaf from the root. The deterministic complexity (also called the decision tree complexity) of a Boolean function f, denoted by D(f), is the minimum of c(A) over all deterministic algorithms A for f, so that [math]D(f) = \min_A \max_x c(A,x).[/math][1]
It can be shown that if [math]D(f)=n[/math] if and only if the function f is evasive.
- ↑ Christophe Garban and Jeffrey E Steif. Noise sensitivity of Boolean functions and percolation. Vol. 5. Cambridge University Press, 2014.
