Lecture Notes on Evasiveness of Graph Properties
|Authors:||Lovasz, Laszlo, Young, Neal|
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.