  In this paper, we initiate study of the computational power of adaptive and
non-adaptive monotone decision trees - decision trees where each query is a
monotone function on the input bits. In the most general setting, the monotone
decision tree height (or size) can be viewed as a measure of non-monotonicity
of a given Boolean function. We also study the restriction of the model by
restricting (in terms of circuit complexity) the monotone functions that can be
queried at each node. This naturally leads to complexity classes of the form
DT(mon-C) for any circuit complexity class C, where the height of the tree is
O(log n), and the query functions can be computed by monotone circuits in the
class C. In the above context, we prove the following characterizations and
bounds.
  For any Boolean function f, we show that the minimum monotone decision tree
height can be exactly characterized (both in the adaptive and non-adaptive
versions of the model) in terms of its alternation (alt(f) is defined as the
maximum number of times that the function value changes, in any chain in the
Boolean lattice). We also characterize the non-adaptive decision tree height
with a natural generalization of certification complexity of a function.
Similarly, we determine the complexity of non-deterministic and randomized
variants of monotone decision trees in terms of alt(f).
  We show that DT(mon-C) = C when C contains monotone circuits for the
threshold functions (for e.g., if C = TC0). For C = AC0, we are able to show
that any function in AC0 can be computed by a sub-linear height monotone
decision tree with queries having monotone AC0 circuits. To understand the
logarithmic height case in case of AC0 i.e., DT(mon-AC0), we show that
functions in DT(mon-AC0) have AC0 circuits with few negation gates.
