Paul Beame, Widad Machmouchi

We prove a time-space tradeoff lower bound of $T =

\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ for

randomized oblivious branching programs to compute $1GAP$, also

known as the pointer jumping problem, a problem for which there is a

simple deterministic time $n$ and space $O(\log n)$ RAM (random

access machine) algorithm.

In ... more >>>