Abstract:
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 size $\mbox{exp}\left\{\Omega\left(n^{1/k+1}2^{-2k} k^{-4}\right)\right\}$ to be computed by any read-$k$-times branching program. The result actually gives the strongest possible separation --- the exponential lower bound applies to both non-deterministic read-$k$-times branching programs and randomized read-$k$-times branching programs with 2-sided error $\varepsilon$, for some $\varepsilon > 0$. The only previously known results are the separation between $k=1$ and $k=2$~\cite{brs93} and a separation of non-deterministic read-$k$ from deterministic read-$(k\ln k/\ln 2 + C)$, where $C$ is some appropriate constant, for each $k$~\cite{okol97}. A simple corollary of our results is that randomization is not more powerful than non-determinism for read-$k$-times branching programs. A combinatorial result that we prove along the way is a ``hash-mixing lemma'' (see~\cite{mnt90}) for families of hash functions that are {\em almost\/} universal, which may be of independent interest.