Size-Space Tradeoffs for Oblivious Computations

摘要

A major area of interest in computation complexity is the development of lower bounds on the simultaneous resource requirements of algorithmic solutions to a particular problem. Significant relationships can exist between the various parameters influencing the cost of computing such as a radeoff, for which it is impossible to achieve two resource values simultaneously. A new type of tradeoff is introduced that relates the resources of circuit size and space for certain oblivious algorithms. It is demonstrated that for graphs associated with the problems of oblivious merging and pattern matching, restricting the minimal space necessary to compute outputs implies that the graphs have nonoptimal size. These results are direct consequences of a more general result relating the depth and path length of a binary tree to its space requirement.