Title: Making Branching Programs Oblivious Requires Superlogarithmic Overhead
Speaker: Paul Beame, IAS, University of Washington
Date: Wednesday, January 26, 2011 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
An algorithm is oblivious (sometimes also called input-oblivious) if and only if its every operation, operand, as well as the order of those operations is determined independent of its input. Certain models of computation, such as circuits or straight-line programs are inherently oblivious. However, many computing models such as Turing machines and random access machines (RAMs) are not, though moderately efficient simulations of these general models by their more restricted oblivious variants are known.
By considering the out-degree 1 graph reachability problem, also known as 1GAP or the pointer jumping problem, we show that either a superlogarithmic increase in time or a large increase in space is necessary for any randomized oblivious simulation of general RAMs. For example, 1GAP can be solved in linear time and log-space on a RAM but requires T=Omega(n log (n/S) loglog (n/S)) for any randomized oblivious RAM. We show similar though incomparable results for Boolean branching programs.
Joint work with Widad Machmouchi.