Decision tree complexity

A decision tree is a tree representing the logical structure of certain algorithms on various inputs. The nodes of the tree represent branch points of the computation — places where more than one outcome are possible based on some predicate of the input — and the leaves represent possible outcomes. Given a particular input, one starts at the root of the tree, performs the test at that node, and descends accordingly into one of the subtrees of the root. Continuing in this way, one reaches a leaf node which represents the outcome of the computation.

Bit query decision trees

Given a function [math]f:\{-1,1\}^n \to \{-1,1\}[/math], a simple decision tree for the function is a binary tree whose internal nodes have labels from [math]\{1, 2, . . . , n\}[/math] and whose leaves have labels from [math]\{-1, 1\}[/math]. If a node has label i, then the test performed at that node is to examine the ith bit of the input. If the result is -1, one descends into the left subtree, whereas if the result is 1, one descends into the right subtree. The label of the leaf so reached is the value of the function on the input. While it is clear that any such function f has a simple decision tree, we will be interested in simple decision trees for f which have minimal depth decision tree complexity D(f). D(f) is called the deterministic decision tree complexity of f.

Deterministic 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] It can be shown that if [math]D(f)=n[/math] if and only if the function f is evasive.

Randomized decision tree complexity

The randomized complexity of a Boolean function f, denoted by R(f), is the minimum of c(A) over all randomized algorithms A for f, so that [math]D(f) = \min_A \max_x c(A,x).[/math] The cost [math]c(A,x)[/math] can also be seen as the expected number of queries performed on input x, where we use a distribution D over deterministic algorithms, so that [math]R(f) = \min_{D} \max_x \mathbb{E}_A^{D}[c(A,x)],[/math]

Level-p complexity

The level-p-complexity of a Boolean function f, denoted by [math]D_p(f)[/math], is the minimum over all (deterministic) algorithms A for f of the expected number of questions that are asked when the input has distribution [math]\pi_p[/math], so that [math]D_p(f) = \min_A \mathbb{E}_x^{\pi_p}[c(A,x)],[/math] where [math]\mathbb{E}_x^{\pi_p}[c(A,x)][/math] denotes the expectation of c(A,x) when [math]x\sim \pi_p[/math]. We use the distribution [math]\pi_p[/math] which means that the input bits are i.i.d. with Bernoulli distribution with parameter [math]p \in (0,1)[/math].