@Article{RV76b,
  author = 	 { Ronald L. Rivest and Jean Vuillemin },
  title = 	 { On recognizing graph properties from adjacency matrices },
  journal = 	 { Theoretical Computer Science },
  OPTyear = 	 { 1976 },
  OPTmonth = 	 { December },
  date =         { 1976-12 },                  
  pages = 	 { 371--384 },
  volume = 	 { 3 },
  number = 	 { 3 },
  publisher =    { North-Holland },                   
  doi =          { 10.1016/0304-3975(76)90053-0 },                    
  abstract =     {
      A conjecture of Aanderaa and Rosenberg [5] motivates this work.
      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 $C(P)=d$ whenver $P(0^d)\ne P(1^d)$ and $P$ is invariant under
      a transitive permutation group acting on the arguments.  A 
      non-constructive argument (not based on the construction of an
      ``oracle'') settles this question for $d$ a prime power.  We use
      this result to prove the Aanderaa-Rosenberg conjecture: at least
      $v^2/16$ 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.
  },
}