Super-linear time-space tradeoff lower bounds for randomized computation.

Paul Beame Michael E. Saks Xiaodong Sun Erik Vee

Published in: FOCS (2000)

Keyphrases

lower bound
worst case
upper bound
branch and bound algorithm
space time
previously computed
randomized algorithm
linear space
search space
decision trees
vector space
trade off
computational complexity
low dimensional
greedy algorithm
higher dimensional
upper and lower bounds
optimal solution