** Next:** Graph Properties:
** Up:** Preliminaries
** Previous:** Deterministic Decision Trees:
** Contents**

####

Evasive Functions:

Any *N*-bit Boolean function *f* has a deterministic decision tree
complexity associated with it. An *N*-bit Boolean function is
*evasive* if and only if its deterministic decision tree
complexity is *N*. Some evasive graph properties are connectivity,
bipartiteness, is the graph a tree, and does the graph have *k* edges.
Evasive functions are then the hardest problems in the classical
oracle query model; for some input we are required to examine every
possible edge. The nonconstant symmetric functions AND, OR, MAJORITY,
and PARITY of Section 2.6 are evasive; indeed, all
nonconstant symmetric function are evasive (consider two consecutive
Hamming weights the function differs on, *a* and *a* + 1, the adversary
answers 1 to the first *a* queries, and 0 to the rest).

** Next:** Graph Properties:
** Up:** Preliminaries
** Previous:** Deterministic Decision Trees:
** Contents**
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository