Tree Functions

Tree functions are Boolean functions of $N$ bits that can be written as a disjunction of conjunctions in which each of the $N$ variables occurs exactly once. Tree functions are evasive in the classical case [14].

Theorem 4.1.1   $\Omega(\sqrt[4]{N})$ oracle queries are required to compute any tree function of $N$ bits in the bounded error setting.

This lower bound is a special case of the $\Omega(\sqrt[4]{D(f)})$ lower bound for monotone functions proved by Beals et al. [2], as tree functions are monotone functions with decision tree complexity $N$. Here we see for the first time a gap that is not quadratic with the classical case. While this lower bound agrees with the result for monotone functions, the author believes it is not asymptotically tight. Whether there is an $\Omega(\sqrt{N})$ lower bound for computing $N$-bit tree functions is an open question.