  In the decision tree computation model for Boolean functions, the depth
corresponds to query complexity, and size corresponds to storage space. The
depth measure is the most well-studied one, and is known to be polynomially
related to several non-computational complexity measures of functions such as
certificate complexity. The size measure is also studied, but to a lesser
extent. Another decision tree measure that has received very little attention
is the minimal rank of the decision tree, first introduced by Ehrenfeucht and
Haussler in 1989. This measure is closely related to the logarithm of the size,
but is not polynomially related to depth, and hence it can reveal additional
information about the complexity of a function. It is characterised by the
value of a Prover-Delayer game first proposed by Pudl\'ak and Impagliazzo in
the context of tree-like resolution proofs. In this paper we study this measure
further. We obtain an upper bound on depth in terms of rank and Fourier
sparsity. We obtain upper and lower bounds on rank in terms of (variants of)
certificate complexity. We also obtain upper and lower bounds on the rank for
composed functions in terms of the depth of the outer function and the rank of
the inner function. This allow us to easily recover known asympotical lower
bounds on logarithm of the size for Iterated AND-OR and Iterated 3-bit
Majority. We compute the rank exactly for several natural functions and use
them to show that all the bounds we have obtained are tight. We also show that
rank in the simple decision tree model can be used to bound query complexity,
or depth, in the more general conjunctive decision tree model. Finally, we
improve upon the known size lower bound for the Tribes function and conclude
that in the size-rank relationship for decision trees, obtained by Ehrenfeucht
and Haussler, the upper bound for Tribes is asymptotically tight.
