Abstract
The 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. For different computations the sets of re-tested variables may be different. Hence, $R$ lies between $0$ and $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=\epsilon n$ for a constant $\epsilon > 0$. This also gives a new and simple proof of an exponential lower bound for branching programs of length $1+\epsilon)n$.These lower bounds are proved for quadratic functions of Ramanujan graphs.