Expanders and time-restricted branching programs

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; the sets of variables re-tested along different computations may be different. For every branching program, this number lies between 0 (read-once programs) and the total number n of variables (general branching programs). The best results so far were exponential lower bounds on the size of branching pro-grams with R = o(n / log n). We improve this to R ≤ ɛn for a constant ɛ> 0. As a byproduct, this provides a simple alternative proof of an exponential lower bound for (1 + ɛ)n time branch-ing programs for a constant ɛ> 0. These lower bounds are proved for quadratic functions of Ramanujan graphs