TR00-025 Authors: Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee

Publication: 23rd May 2000 10:02

Downloads: 2097

Keywords:

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 in his time-space tradeoffs for

deterministic RAM algorithms computing element distinctness and for

Boolean branching programs computing a natural quadratic form.

Ajtai's bounds were of the following form: if the machine uses at most

$kn$ time for some constant $k$ it requires space at least

$\epsilon_k n$ for some constant $\epsilon_k$. In this paper we

provide an explicit relationship between $\epsilon_k$ and $k$ that

achieves larger lower bounds than those proven by Ajtai.

In particular, we obtain time-space tradeoff lower

bounds of the form $T=\Omega(n\sqrt{\log/\log\log (n/S)})$, which

implies that if the space is $n^{1-\epsilon}$ then

the time used is $\Omega(n\sqrt{\log /\log\log (n)})$.