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

We prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques are an extension of those used by Ajtai 14, 51 in his time-space tradeoffs for deterministic RAM algorithms computing element distinctness and for deterministic Boolean branching programs computing an explicit function based on quadratic forms over GF(2). Our results also give a quantitative improvement over those given by Ajtai. Ajtai shows, for certain spec$c func-tions, that any branching program using space S = o(n) requires time T that is superlineal: The functional form of the superlinear bound is not given in his paper. but optimizing the parameters in his arguments gives T = R(n log log n / log log log n) for S = O(n'-'). For the same functions considered by Ajtai, we prove a time-space tradeoff of the form T = R(ndlog(n/S) / loglog(n/S)). Inparticu-lar. for space O(n'-'), this improves the lower bound on time to R(nJ1og n / log log n).