Lecture Notes on Evasiveness of Graph Properties

Abstract

This report presents notes from the first eight lectures of the class Many Models of Complexity taught by Laszlo Lovasz at Princeton University in the fall of 1990. The topic is evasiveness of graph properties: given a graph property, how many edges of the graph an algorithm must check in the worst case before it knows whether the property holds.

Tech. Rep. CS-TR-317-91, Computer Science Dept., Princeton University

Cited by in corpus (6)

• Evasiveness of Graph Properties and Topological Fixed-Point Theorems
• New separation between $s(f)$ and $bs(f)$
• On the Sensitivity Complexity of $k$-Uniform Hypergraph Properties
• From Exact Learning to Computing Boolean Functions and Back Again
• Between the deterministic and non-deterministic query complexity
• A note on graphs with disjoint maximal cliques ans a link with evasiveness