The decision-tree complexity of a function f measures how much information an algorithm needs about x to compute f(x). A function f is evasive if, in the worst case, an algorithm needs complete information about x to compute f(x).
I'll present several results on evasiveness of graph properties (boolean-valued functions on graphs), including:
all monotone bipartite graph properties are evasive
all monotone graph properties are near-evasive: any algorithm that decides the property requires at least a fixed fraction of complete information about the input in the worst case
The proofs of these results use interesting techniques from algebraic topology and group theory.
The above results are all proved for deterministic algorithms. Time permitting, I'll discuss decision-tree complexity for nondeterministic and randomized algorithms, and list some of the lower-bound results for graph properties in these models.
Laszlo Lovasz's lecture notes on graph evasiveness are online.