### Time-space trade-off lower bounds for randomized computation of decision problemsTime-space trade-off lower bounds for randomized computation of decision problems

Access Restriction
Subscribed

 Author Beame, Paul ♦ Saks, Michael ♦ Sun, Xiaodong ♦ Vee, Erik Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2003 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Branching programs ♦ Element distinctness ♦ Quadratic forms ♦ Random-access machines Abstract We prove the first time-space lower bound trade-offs 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 extension of those used by Ajtai and by Beame, Jayram, and Saks that applied to deterministic branching programs. Our results also give a quantitative improvement over the previous results.Previous time-space trade-off results for decision problems can be divided naturally into results for functions with Boolean domain, that is, each input variable is {0,1}-valued, and the case of large domain, where each input variable takes on values from a set whose size grows with the number of variables.In the case of Boolean domain, Ajtai exhibited an explicit class of functions, and proved that any deterministic Boolean branching program or RAM using space $\textit{S}$ = $\textit{o}(\textit{n})$ requires superlinear time $\textit{T}$ to compute them. The functional form of the superlinear bound is not given in his paper, but optimizing the parameters in his arguments gives $\textit{T}$ = $Ω(\textit{n}$ log log $\textit{n}/log$ log log $\textit{n})$ for $\textit{S}$ = $O(n^{1™&epsis;}).$ For the same functions considered by Ajtai, we prove a time-space trade-off (for randomized branching programs with error) of the form $\textit{T}$ = $Ω(\textit{n}$ &sqrt; $log(\textit{n/S})/log$ log $(\textit{n/S})).$ In particular, for space $O(n^{1™&epsis;}),$ this improves the lower bound on time to $Ω(\textit{n}&sqrt;$ log $\textit{n}/log$ log $\textit{n}).In$ the large domain case, we prove lower bounds of the form $\textit{T}$ = $Ω(\textit{n}&sqrt;$ $log(\textit{n/S})/log$ log $(\textit{n/S}))$ for randomized computation of the element distinctness function and lower bounds of the form $\textit{T}$ = $Ω(\textit{n}$ log $(\textit{n/S}))$ for randomized computation of Ajtai's Hamming closeness problem and of certain functions associated with quadratic forms over large fields. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2003-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 50 Issue Number 2 Page Count 42 Starting Page 154 Ending Page 195

#### Open content in new tab

Source: ACM Digital Library