@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.                  
             },  
}