|hash specifics: GOOD NEWS firstname.lastname@example.org (Thilo Ernst) (1990-12-17)|
|Re: hash specifics: GOOD NEWS email@example.com (1990-12-19)|
|From:||firstname.lastname@example.org (Jeff Jenness)|
|Organization:||University of Missouri - Rolla|
|Date:||Wed, 19 Dec 90 13:17:38 CST|
In article <9012171443.AA18297@prosun.first.gmd.de> Thilo Ernst <email@example.com> writes:
>In a 1985 paper in Comm. of the ACM, T.J. Sager of the University of Missouri
>presented the so-called mincycle algorithm for computing perfect (collision-
>free) hash functions.
>Although the problem is nasty (NP-complete) in general, the algorithm
>was shown to work in polynomial time for virtually all cases.
Dr. Sager is working on his algorithm and feels that he has some better
results. In the paper in the CACM he claimed that the algorithm ran in
polynomial time where the degree was the 6th power. He feels that the
algorithm is actually O(n^3). He has some software running on an IBM PC
in Turbo Pascal that he is making available(he asks $10 for the cost of
the software, if you provide a disk and mailer). If you wish to find out
how to get it then write me email and I will respond individually. There
has also been some work done elsewhere to improve upon the results of Dr.
Sager by providing a better set of "pseudo random" hash function. If
time permits, I will construct a bibliography on the papers that I have
University of Missouri - Rolla
Return to the
Search the comp.compilers archives again.