Path: utzoo!attcan!telly!lethe!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!usc!snorkelwacker.mit.edu!hsdndev!spdcc!iecc!compilers-sender From: jeffj@cs.umr.edu (Jeff Jenness) Newsgroups: comp.compilers Subject: Re: hash specifics: GOOD NEWS Keywords: design Message-ID: <9012191917.AA21299@umrcsa.local> Date: 19 Dec 90 19:17:38 GMT References: <9012171443.AA18297@prosun.first.gmd.de> Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: jeffj@cs.umr.edu (Jeff Jenness) Organization: University of Missouri - Rolla Lines: 25 Approved: compilers@iecc.cambridge.ma.us In article <9012171443.AA18297@prosun.first.gmd.de> Thilo Ernst 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 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.