ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



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



ISSN 1433-8092 | Imprint