  Relations between the decision tree complexity and various other complexity
measures of Boolean functions is a thriving topic of research in computational
complexity. It is known that decision tree complexity is bounded above by the
cube of block sensitivity, and the cube of polynomial degree. However, the
widest separation between decision tree complexity and each of block
sensitivity and degree that is witnessed by known Boolean functions is
quadratic. In this work, we investigate the tightness of the existing cubic
upper bounds.
  We improve the cubic upper bounds for many interesting classes of Boolean
functions. We show that for graph properties and for functions with a constant
number of alternations, both of the cubic upper bounds can be improved to
quadratic. We define a class of Boolean functions, which we call the zebra
functions, that comprises Boolean functions where each monotone path from 0^n
to 1^n has an equal number of alternations. This class contains the symmetric
and monotone functions as its subclasses. We show that for any zebra function,
decision tree complexity is at most the square of block sensitivity, and
certificate complexity is at most the square of degree.
  Finally, we show using a lifting theorem of communication complexity by
G{\"{o}}{\"{o}}s, Pitassi and Watson that the task of proving an improved upper
bound on the decision tree complexity for all functions is in a sense
equivalent to the potentially easier task of proving a similar upper bound on
communication complexity for each bi-partition of the input variables, for all
functions. In particular, this implies that to bound the decision tree
complexity it suffices to bound smaller measures like parity decision tree
complexity, subcube decision tree complexity and decision tree rank, that are
defined in terms of models that can be efficiently simulated by communication
protocols.
