Space-Time Tradeoffs for Graph Properties

. We initiate a study of space-time tradeoffs in the cell-probe model under restricted preprocessing power. Classically, space-time tradeoffs have been studied in this model under the assumption that the preprocessing is unrestricted. In this setting, a large gap exists between the best known upper and lower bounds. Augmenting the model with a function family F that characterizes the preprocessing power, makes for a more realistic computational model and allows to obtain much tighter space-time tradeoffs for various natural settings of F. The extreme settings of our model reduce to the classical cell probe and generalized decision tree complexities. We use graph properties for the purpose of illustrating various aspects of our model across this broad spectrum. In doing so, we develop new lower bound techniques and strengthen some existing results. In particular, we obtain near-optimal space-time tradeoffs for various natural choices of F; strengthen the Rivest-Vuillemin proof of the f..