---- dataentry seminar ----
date_dt : 2011-07-22
title : Time-space tradeoffs for randomized oblivious branching programs
speaker : Widad Machmouchi
affiliation : University of Washington
time : 16h15
room : BC 129
table : seminars
===================
template:datatemplates:seminar
-----------------------


==== abstract ====
We prove a time-space tradeoff lower bound of T = Omega(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 = Omega(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(\og^2 n) 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=omega(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.