TR98-053 Authors: Paul Beame, Michael Saks, Jayram S. Thathachar

Publication: 31st August 1998 16:58

Downloads: 1173

Keywords:

We obtain the first non-trivial time-space tradeoff lower bound for

functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a

Boolean function f that requires exponential size to be computed by any

branching program of length cn, for some constant c>1. We also give the first

separation result between the syntactic and semantic read-k models for k>1 by

showing that polynomial-size semantic read-twice branching programs can compute

functions that require exponential size on any syntactic read-k branching

program. We also show a time-space tradeoff result on the more general

R-way branching program model: for any k, we give a function that requires

exponential size to be computed by length kn q-way branching programs, for

some q=q(k).

Comment #1 Authors: Paul Beame, Michael Saks, Jayram S. Thathachar

Accepted on: 17th September 1998 14:34

Downloads: 1800

Keywords: