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 all k ? 0, as conjectured by various authors [Weg87, SS93, Pon95]. For every k, we exhibit two explicit functions that can be computed by linear-sized read-(k+1)-times branching programs but require size exp n\Omega i n 1=k+1 2 \Gamma2k k \Gamma4 jo 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 ", for some " ? 0. The only previously known results are the separation between k = 1 and k = 2 [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 [Oko97]. A simple corollary of our result..