Boolean Functions

In this chapter we consider increasingly general classes of functions. We first examine lower bounds for tree functions in Section and prove $\Omega(\sqrt[4]{N})$ oracle queries are required to compute a tree function of $N$ bits.

We define nondeterministic decision tree complexity in Section . We then prove that $\Omega(\sqrt{N})$ oracle queries are required to compute any $N$ bit Boolean function with nondeterministic decision tree complexity $N$ in Section . Finally in Section we present our most general result: $\Omega(\sqrt[4]{D(f)})$ oracle queries are required to compute a class of Boolean functions that meet a sensitivity condition and have deterministic decision tree complexity $D(f)$.