Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-025 | 20th May 2000 00:00

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


Authors: Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee
Publication: 23rd May 2000 10:02
Downloads: 978


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)})$.

ISSN 1433-8092 | Imprint