TR98-002 Authors: Jayram S. Thathachar

Publication: 13th January 1998 12:41

Downloads: 2763

Keywords:

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.