A generalization of a lower bound technique due to Fredman and Saks

In a seminal paper of 1989, Fredman and Saks proved lower bounds for some i mportant data-structure problems in the cell probe model. In particular, lo wer bounds were established on worst-case and amortized operation cost for the union-find problem and the prefix sum problem. The goal of this paper i s to turn their proof technique into a general tool that can be applied to different problems and computational models. To this end we define two quan tities: Output Variability depends only on the model of computation. It ind icates how much variation can be found in the results of a program with cer tain resource bounds. This measures in some sense the power of a model. Pro blem Variability characterizes in a similar sense the difficulty of the pro blem. Our Main Theorem shows that by comparing a model's output variability to a problem's problem variability, lower bounds on the complexity of solving th e problem on the given model may be inferred. The theorem thus shows how to separate the analysis of the model of computation from that of the problem when proving lower bounds. We show how the results of Fredman and Saks fit our framework by computing the output variability of the cell probe model and the problem variability for problems considered in their paper. This allows us to reprove their low er bound results, and slightly extend them. The main purpose of this paper though is to present the generalized technique.