Re: hash specifics: GOOD NEWS

In article <9012171443.AA18297@prosun.first.gmd.de> Thilo Ernst <te@prosun.first.gmd.de> 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
on MPHF's.


Jeff Jenness
University of Missouri - Rolla
jeffj@cs.umr.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.