@InProceedings{RV75,
replaced-by = { RV76b },
author = { Ronald L. Rivest and Jean Vuillemin },
title = { A Generalization and Proof of the {Aanderaa-Rosenberg} Conjecture },
pages = { 6--11 },
url = { http://doi.acm.org/10.1145/800116.803747 },
doi = { 10.1145/800116.803747 },
acmid = { 803747 },
acm = { 08205 },
booktitle = { Proceedings of seventh annual ACM symposium on Theory of computing },
editor = { William C. Rounds },
date = { 1975 },
OPTyear = { 1975 },
OPTmonth = { May 5--7, },
eventtitle = { STOC '75 },
eventdate = { 1975-05-05/1975-05-07 },
venue = { Albuquerque, New Mexico },
publisher = { ACM },
organization = { ACM },
abstract = {
We investigate the maximum number $C(P)$ of arguments of $P$ that must
be tested in order to compute $P$, a Boolean function of $d$ Boolean
arguments. We present evidence for the general conjecture that that
$C(P)=d$ whenever $P(0^d)\ne P(1^d)$ and $P$ is left invariant by
a transitive permutation group acting on its arguments. A non-constructive
argument (not based on the construction of an ``oracle'') proves the
generalized conjecture for $d$ a prime power. We use this result to
prove the Aanderaa-Rosenberg conjecture by showing that at least
$v^2/9$ entries of the adjacency matrix of a $v$-vertex undirected graph
$G$ must be examined in the worst case to determine if $G$ has any
given non-trivial monotone graph property.
},
}