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

Our computational model is a random access machine with $n$ read only input registers each containing $ c \log n$ bits of information and a read and write memory. We measure the time by the number of accesses to the input registers. We show that for all $k$ there is ... more >>>