We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. The soft rank is a somehow relaxed variant of the rank. Among all decision trees of depth d, the complete binary decision tree (the most balanced tree) has maximum soft rank d, the decision list (the most unbalanced tree) has minimum soft rank √d, and any other trees have soft rank between √d and d. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f.
Let M be a bridgeless matroid on ground set {1,...,n} and fM:{0,1}n→{0,1} be the indicator function of its independent sets. A folklore fact is that fM is evasive, i.e., D(fM)=n where D(f) denotes the deterministic decision tree complexity of f. Here we prove query complexity lower bounds for fM in three stronger query models: (a) D⊕(fM)=Ω(n), where D ⊕ (f) denotes the parity decision tree complexity of f; (b) R(fM)=Ω(n/logn), where R(f) denotes the bounded error randomized decision tree complexity of f; and (c) Q(fM)=Ω(n), where Q(f) denotes the bounded error quantum query complexity of f.
This chapter focuses on query complexity, which measures the minimum number of input bits that need to be read to solve a problem, in other words, the minimum depth of any correct decision tree (or branching program). Techniques for upper and lower bounds for deterministic and randomized query complexities are covered. The close relationships between query complexity and other measures known as certificate complexity and sensitivity are also covered. The chapter concludes with techniques for proving lower bounds on the size (as opposed to depth) of decision trees and branching programs.