Removing Ramsey theory: Lower bounds with smaller domain size

AbstractBoppana (1989) 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 is 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 has forced the domain size to be large)