tag:blogger.com,1999:blog-8890204.post9002634568555928026..comments2022-11-19T05:18:34.338-05:00Comments on My Biased Coin: New Preprint: An Analysis of Random-Walk Cuckoo HashingMichael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-8890204.post-27146005270014059192009-04-14T11:02:00.000-04:002009-04-14T11:02:00.000-04:00A small theorem in the paper, not directly related...A small theorem in the paper, not directly related to the random-walk, is that a better bound on the running time of the BFS insertion method.<br /><br />We can now show (1/epsilon)^O(1) instead of (1/epsilon)^O(log d), and <br />in fact the O(1) is decreasing in d and converges to 1.<br /><br />This partially answers some of the questions in the comments of your earlier post on cuckoo hashing.Pall Melstedhttps://www.blogger.com/profile/04606222181560129813noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-22870102608937098262009-04-13T12:24:00.000-04:002009-04-13T12:24:00.000-04:00Your link seems broken, but http://www.math.cmu.ed...Your link seems broken, but http://www.math.cmu.edu/~af1p/Texfiles/cuckoo.pdf works.Anonymousnoreply@blogger.com