Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Should tables be sorted? Yes but--- a question

Expand Messages
  • GASARCH
    In Yao s paper Should tables be sorted he did the following (I am paraphrasing alot). A (U,n;q)-WPDS (Word Probe Data Structure) for MEM is the following; - A
    Message 1 of 1 , Nov 24, 2008
    • 0 Attachment
      In Yao's paper Should tables be sorted he did the following (I am paraphrasing alot).

      A (U,n;q)-WPDS (Word Probe Data Structure) for MEM is the following;
      1. 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[1],...,CELL[n].
      2. (Assume Step 1 has been done so there are elements in CELL[1],...,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.
      Thoughts, results, and a question I really want someone to answer.
      1. I call it a WBDS to distinguish from the bit probe model.
      2. The obvious appraoch would be to SORT the elements of A and use binary search. Hence q=log(n+1).
      3. For some cases where U is small compared to n, there are constant-probe algorithms.
      4. 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.
      5. 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!.
      6. 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.


      --
      Posted By GASARCH to Computational Complexity at 11/24/2008 11:00:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.