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 ... more >>>

We obtain an exponential separation between consecutive levels in the hierarchy of classes of functions computable by polynomial-size syntactic read-$k$-times branching programs, for {\em all\/} $k>0$, as conjectured by various authors~\cite{weg87,ss93,pon95b}. For every $k$, we exhibit two explicit functions that can be computed by linear-sized read-$(\kpluso)$-times branching programs but require ... more >>>