Space-time tradeoffs for graph properties

Yevgeniy Dodis, Sanjeev Khanna

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We initiate a study of space-time tradeoffs in the cell-probe model under restricted preprocessing power. Classically, space-time tra- deoffs 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 tigh- Ter 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 famous AKR conjecture to show that no non-trivial monotone graph property can be expressed as a polynomial of sub-quadratic degree; and obtain new results on the generalized decision tree complexity w.r.t. various families F.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540662243, 9783540662242
StatePublished - 1999
Event26th International Colloquium on Automata, Languages and Programming, ICALP 1999 - Prague, Czech Republic
Duration: Jul 11 1999Jul 15 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1644 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other26th International Colloquium on Automata, Languages and Programming, ICALP 1999
Country/TerritoryCzech Republic

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Space-time tradeoffs for graph properties'. Together they form a unique fingerprint.

Cite this