Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-002 | 8th January 1998 00:00

On Separating the Read-k-Times Branching Program Hierarchy


Authors: Jayram S. Thathachar
Publication: 13th January 1998 12:41
Downloads: 2874


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.

ISSN 1433-8092 | Imprint