next up previous contents
Next: Nondeterministic Decision Tree Complexity Up: Boolean Functions Previous: Boolean Functions   Contents


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.


\begin{proof}
% latex2html id marker 2249For any tree function $f$ let $d$ b...
... $c_{max} > \sqrt{N}$ or $d \ge
\sqrt{N}$, and the theorem follows.
\end{proof}

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.


next up previous contents
Next: Nondeterministic Decision Tree Complexity Up: Boolean Functions Previous: Boolean Functions   Contents
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository