Abstract:
The \emph{replication number} of a branching program is the minimum number R such that along every accepting computation at most R variables are tested more than once. Hence 0\leq R\leq n for every branching program in n variables. The best results so far were exponential lower bounds on the size of branching programs with R=o(n/\log n). We improve this to R=cn for a constant c>0. This also gives a new and simple proof of an exponential lower bound of Beame, Saks and Tchathachar for branching programs of length (1+c)n. We prove our lower bounds for quadratic functions of Ramanujan graphs. The proofs are simple.