tag:blogger.com,1999:blog-3722233.post6972764564708295022..comments2021-05-16T09:01:42.816-05:00Comments on Computational Complexity: Should tables be sorted? Yes but--- a questionLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-84493273522775772622008-11-24T22:40:00.000-06:002008-11-24T22:40:00.000-06:00Implicit probe search presents a trade-off between...Implicit probe search presents a trade-off between two parameters:<BR/>1. The size of the domain from which we are given n elements to store<BR/>2. The number of queries we need.<BR/><BR/>Fiat and Naor showed that if you are given a set of size n and the domain size is poly(n), you can perform implicit probe search in constant time. This was improved by Gabzion Shaltiel to a domain size which is quasi polynomial in n. <BR/><BR/>Gabizon and Hassidim showed that you can get o(log n) even when the domain size is exponential in n.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38661753592135411752008-11-24T18:15:00.000-06:002008-11-24T18:15:00.000-06:00I believe what you are asking for is in the paper ...I believe what you are asking for is in the paper "Implicit O(1) probe search" by Fiat and Naor, SICOMP 1993. They show how to search in O(1) time for quite large U, but still much smaller than the Ramsey numbers for which there is a lower bound.Rasmus Paghhttps://www.blogger.com/profile/05722627403861422993noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27734900686267785672008-11-24T15:09:00.000-06:002008-11-24T15:09:00.000-06:00Well, it's not really the cell-probe model. In the...Well, it's not really the cell-probe model. In the cell-probe model, cells can store anything you want, not just the elements in the data structure.<BR/><BR/>People have called this model "implicit data structures" (see work by Munro, Francheschini, Grossi etc). Supposedly, "implicit" means that you're just storing a permutation, and the data structuring is implicit in the order of this permutation.<BR/><BR/>More recent work on dictionaries (that the anonymous commenter alludes to) has focused on the true model, where you can store functions of your data elements in any cell. See work by [Fredman, Komlos, Szemeredi] for randomized dictionaries, and [Hagerup, Miltersen, Pagh], [Pagh], [Ruzic] for deterministic.<BR/><BR/>By now, there is nothing interesting in Yao's paper for computer science, just for people passionate about Ramsey theory.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75128673601623219302008-11-24T13:13:00.000-06:002008-11-24T13:13:00.000-06:00YES this is the CELL PROBE MODEL. I didn't call it...YES this is the CELL PROBE MODEL. I didn't call it that<BR/>since there are two kinds:<BR/>where the cells holds BITS<BR/>and where the cells hold<BR/>WORDS. But YES, it is<BR/>the Cell Probe Model<BR/>and I should have said so.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33149074468244755592008-11-24T13:09:00.000-06:002008-11-24T13:09:00.000-06:00Is WBDS the same thing as cell-probe model?I think...Is WBDS the same thing as cell-probe model?<BR/><BR/>I think it is kind of similiar to the deterministic dictionary problem, which is still open.Anonymousnoreply@blogger.com