Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > OBLIVIOUS ALGORITHMS:
Reports tagged with Oblivious Algorithms:
TR10-104 | 29th June 2010

#### Making RAMs Oblivious Requires Superlogarithmic Overhead

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
simple deterministic time $n$ and space $O(\log n)$ RAM (random