Name
Abstract | ||
|---|---|---|
We prove a time-space tradeoff lower bound of $T =\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ forrandomized oblivious branching programs to compute $1GAP$, alsoknown as the pointer jumping problem, a problem for which there is asimple deterministic time $n$ and space $O(\log n)$ RAM (randomaccess machine) algorithm.%Although no simulations of general%computation on randomized oblivious algorithms requiring only%polylogarithmic increase in time and space are yet known, our lower%bound implies that a superlogarithmic factor increase in time and%space is in fact necessary in any such simulation.We give a similar time-space tradeoff of $T =\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right)$ forBoolean randomized oblivious branching programs computing$GIP$-$MAP$, a variation of the generalized inner product problem thatcan be computed in time $n$ and space $O(\log^2 n)$ by adeterministic Boolean branching program.These are also the first lower bounds for randomized obliviousbranching programs computing explicit functions that apply for$T=\omega(n\log n)$. They also show that any simulation ofgeneral branching programs by randomized oblivious ones requires eithera superlogarithmic increase in time or an exponential increase in space. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/CCC.2011.35 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
Boolean functions,computational complexity,deterministic algorithms,randomised algorithms,1GAP,Boolean randomized oblivious branching program,GIP-MAP,RAM,deterministic Boolean branching program,generalized inner product problem,pointer jumping problem,random access machine algorithm,superlogarithmic overhead,time-space tradeoff,branching programs,lower bounds,oblivious computation,randomization,time-space tradeoffs | Boolean function,Discrete mathematics,Binary logarithm,Combinatorics,Exponential function,Upper and lower bounds,Pointer jumping,Probability distribution,Omega,Mathematics,Computational complexity theory | Conference |
ISSN | ISBN | Citations |
1093-0159 E-ISBN : 978-0-7695-4411-3 | 978-0-7695-4411-3 | 3 |
PageRank | References | Authors |
0.42 | 14 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Beame | 1 | 2234 | 176.07 |
| Widad Machmouchi | 2 | 19 | 2.69 |