Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > UNIVERSAL HASH FAMILIES:
Reports tagged with universal hash families:
TR98-002 | 8th January 1998
Jayram S. Thathachar

#### On Separating the Read-k-Times Branching Program Hierarchy

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

ISSN 1433-8092 | Imprint