Expanders and time-restricted branching programs

AbstractThe 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 programs with R=o(n/logn). We improve this to R≤ϵn for a constant ϵ>0. This also gives an alternative and simpler proof of an exponential lower bound for (1+ϵ)n time branching programs for a constant ϵ>0. We prove these lower bounds for quadratic functions of Ramanujan graphs