Wed, 19 Dec 90 13:17:38 CST

Related articles |
---|

hash specifics: GOOD NEWS te@prosun.first.gmd.de (Thilo Ernst) (1990-12-17) |

Re: hash specifics: GOOD NEWS jeffj@cs.umr.edu (1990-12-19) |

Newsgroups: | comp.compilers |

From: | jeffj@cs.umr.edu (Jeff Jenness) |

Keywords: | design |

Organization: | University of Missouri - Rolla |

References: | <9012171443.AA18297@prosun.first.gmd.de> |

Date: | Wed, 19 Dec 90 13:17:38 CST |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.