TY - JOUR

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

AU - Beame, Paul

AU - Saks, Michael

AU - Sun, Xiaodong

AU - Vee, Erik

PY - 2000

Y1 - 2000

N2 - 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 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 specific functions, that any branching program using space S = o(n) requires time T that is superlinear. The functional form of the superlinear bound is not given in his paper, but optimizing the parameters in his arguments gives T = Ω(n log log n/log log log n) for S = O(n1-ε). For the same functions considered by Ajtai, we prove a time-space tradeoff of the form T = Ω(n√log(n/S)/log log(n/S)). In particular, for space O(n1-ε), this improves the lower bound on time to Ω(n√log n/log log n).

AB - 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 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 specific functions, that any branching program using space S = o(n) requires time T that is superlinear. The functional form of the superlinear bound is not given in his paper, but optimizing the parameters in his arguments gives T = Ω(n log log n/log log log n) for S = O(n1-ε). For the same functions considered by Ajtai, we prove a time-space tradeoff of the form T = Ω(n√log(n/S)/log log(n/S)). In particular, for space O(n1-ε), this improves the lower bound on time to Ω(n√log n/log log n).

UR - http://www.scopus.com/inward/record.url?scp=0034512732&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034512732&partnerID=8YFLogxK

U2 - 10.1109/SFCS.2000.892078

DO - 10.1109/SFCS.2000.892078

M3 - Article

AN - SCOPUS:0034512732

SN - 0272-5428

SP - 169

EP - 179

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

ER -