** Next:** Evasive Functions:
** Up:** Preliminaries
** Previous:** Preliminaries
** Contents**

####

Deterministic Decision Trees:

A decision tree of *N* bits is a rooted binary tree. Each internal
node of the tree contains an index
*i* {1,..., *N*} and has
two children. Each leaf contains either a 1 or a 0. To determine
the value of the deterministic decision tree on an input
*x* {0, 1}^{N} we traverse the tree starting at the root. At each
internal node we examine the *x*_{i}, where *i* is the index stored at
that node. If *x*_{i} = 1 we follow the path through the left
subtree; if *x*_{i} = 0 we follow the path through the right subtree.
The value stored at the leaf that we eventually reach is the output of
the algorithm. Any decision tree computes an *N*-bit Boolean
function. There are many different deterministic decision trees that
compute any given function.

The decision tree complexity of a Boolean function is the minimum
depth of any decision tree that computes that function. We denote the
decision tree complexity of a Boolean function *f* by *D*(*f* ). The
decision tree complexity of a function *f* is just its classical
oracle query complexity. Any decision tree of depth *D*(*f* ) determines
a minimal sequence of oracle queries that allow us to compute *f* (*x*)
for any input *x*.

** Next:** Evasive Functions:
** Up:** Preliminaries
** Previous:** Preliminaries
** Contents**
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository