@InProceedings{Riv74b,
  author = 	 { Ronald L. Rivest },
  title = 	 { On the optimality of {Elias}'s algorithm for performing
                   best-match searches },
  date =         { 1974 },                  
  eventtitle =   { IFIP '74 },                  
  OPTyear = 	 { 1974 },
  OPTmonth = 	 { August 5--10, },
  eventdate =    { 1974-08-05/1974-08-10 },                  
  booktitle =    { Proceedings of IFIP Congress },
  pages = 	 { 678--681 },
  venue = 	 { Stockholm, Sweden },
  editor = 	 { Jack L. Rosenfeld },
  publisher =    { North-Holland },
  organization = { IFIP },
  annote = 	 { This paper unfortunately contains an error in the proof of the theorem in Section~4.
                   The quantity in equation~(8) is not necessarily bounded below by zero, as claimed.
                   Thus the following proof demonstrating the minimal surface area property for
                   spheres does not imply the optimality of Elias's algorithm.  A correct optimality
                   proof is claimed by Aslanyan and Danoyan (2014).
                 },
  abstract =     {
        We examine a hash-coding algorithm due to Elias for retrieving from a file of fixed-length
        binary records all the ``best-matches'' (using the Hamming distance) to a given input word.
        We prove that no balanced hash-coding algorithm can examine fewer buckets on the average
        than Elias's algorithm does, assuming that every record is equally likely to appear in the
        file.                  
                 },
}