__
TR05-079 | 25th July 2005 00:00
__

#### Expanders and time-restricted branching programs

**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.