Removing Ramsey Theory: Lower Bounds With Smaller Domain Size

: Boppana [B89] proves a lower bound separating the PRIORITY and the COMMON PRAM models that is optimal to within a constant factor. However, an essential ingredient in his proof is a problem with an enormously large input domain. In this paper, I achieve the same lower bound with the improvement that it applies even when the computational problem is defined on a much more reasonably sized input domain. My new techniques provide a greater understanding of the partial information a processor learns about the input. In addition, I define a new measure of the dependency that a function has on a variable and develop new set theoretic techniques to replace the use of Ramsey theory (which had forced the domain size to be large). 1 Introduction Ramsey Theory has been extremely useful in proving lower bounds for problems defined on huge input domains. (e.g, [B89]). Given a fixed algorithm, the input domain is restricted so that the given algorithm, when run on the restricted domain, falls wit..