A (U,n;q)-WPDS (Word Probe Data Structure) for MEM is the following;
- A function that does the following: Given A\substeq U, |A|=n, return the elements of A in some order. Think of them as being in CELL,...,CELL[n].
- (Assume Step 1 has been done so there are elements in CELL,...,CELL[n].) Given u\in U we want to know if u\in A. We have a query algorithm that asks q adpative queries of the form What is in CELL[i]?, and then outputs YES or NO. If YES then u\in A, if NO then u\notin A.
- I call it a WBDS to distinguish from the bit probe model.
- The obvious appraoch would be to SORT the elements of A and use binary search. Hence q=log(n+1).
- For some cases where U is small compared to n, there are constant-probe algorithms.
- KEY: Yao showed that if U is large compared to n then sorting IS the best you can do. How big? Let R(a,b,c) be the RAMSEY number associated to a-uniform hypergraphs, b-sized monochromatic sets, and c colors. Yao showed that if U\ge R(n,2n-1,n!) then sorting is optimal.
- QUESTION: Is a lower value known? I have looked in various places but couldn't find a lower value. However, this may be a case where I'm better off asking an expert. I hope one is reading this blog!.
- This is one of the first applications of Ramsey Theory to computer science. It may be the first, depending on how you defined application, Ramsey Theory, and computer science.