tag:blogger.com,1999:blog-786333285568106173.post798426631146542919..comments2022-04-03T16:08:02.581-04:00Comments on WebDiarios de Motocicleta: Better Guarantees for Chaining and Linear ProbingMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-786333285568106173.post-136405959019307262010-02-05T13:34:09.927-05:002010-02-05T13:34:09.927-05:00Well, I assume all bounds are for worst-case input...Well, I assume all bounds are for worst-case input, since this is what 99% of TCS is about. Whenever we are doing something else, we say it explicitly (average case algorithms, distributional complexity, adaptive algorithms, competitive algorithms, etc). So I don't think there's a need to specify that you analyze your algorithms for worst-case data.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-11718780910630551442010-02-04T21:04:47.674-05:002010-02-04T21:04:47.674-05:00I've been enjoying your latest sequence of pos...I've been enjoying your latest sequence of posts on chernoff bounds and hashing.<br /><br />Just want to clarify your usage of worst case. I agree that worst case typically modifies the input (and not the coins). But what name do you give to the running time of a randomized algorithm with a performance guarantee that holds for the worst case input? "Worst case" doesn't seem quite right. I like your use of "worst case w.h.p."; would you use "expected worst case" if you only have the guarantee in expectation?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-82039359014041724602010-02-03T09:26:16.872-05:002010-02-03T09:26:16.872-05:00Yes, there is some association to cell-probe, but ...Yes, there is some association to cell-probe, but I think it's not the main point. As I said in the post, I think it's more about the external memory model. The performance of hash tables is largely dictated by memory performance, and the cache really is much faster...<br /><br />At some level, cell-probe upper bounds are the same as external memory upper bounds, if you define the cell to be of page size. Indeed, the external memory model tends to only focus on the number of locations probed, just like cell-probe. (With the extra useful guarantee that the algorithm is somewhat realistic, and doesn't invoke the halting problem in the middle or stuff like that...)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-80294401046481879792010-02-03T09:03:49.162-05:002010-02-03T09:03:49.162-05:00Interesting performance guarantee: A bound on the ...Interesting performance guarantee: A bound on the number of distinct memory cells accessed during T operations.<br /><br />This sounds like the cell-probe model. Have anyone used a model like for upper bounds before?Anonymoushttps://www.blogger.com/profile/06328185728688465505noreply@blogger.com