Making Branching Programs Oblivious Requires Superlogarithmic Overhead
Paul W. Beame, Widad Machmouchi · 2011
We prove a time-space tradeoff lower bound of T = Ω (n log(n/s) log log(n/s)) 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. We give a similar time-space tradeoff of T = Ω (n log(n/s) log log(n/s)) for Boolean randomized oblivious branching programs computing GIP-MAP, a variation of the generalized inner product problem that can be computed in time n and space O(log2n) by a deterministic Boolean branching program. These are also the first lower bounds for randomized oblivious branching programs computing explicit functions that apply for T = ω(n log n). They also show that any simulation of general branching programs by randomized oblivious ones requires either a superlogarithmic increase in time or an exponential increase in space.