Lecture Notes on Evasiveness of Graph Properties

Abstract:

These notes cover the first eight lectures of the class Many Models of
Complexity taught by L'aszl'o Lov'asz at Princeton University in the Fall
of 1990. The first eight lectures were on evasiveness of graph properties and
related topics; subsequent lectures were on communication complexity and
Kolmogorov complexity and are covered in other sets of notes.
The fundamental question considered in these notes is, given a function, how
many bits of the input an algorithm must check in the worst case before it
knows the value of the function. The algorithms considered are deterministic,
randomized, and non-deterministic. The functions considered are primarily
graph properties --- predicates on edge sets of graphs invariant under
relabeling of the edges.