Expanders and time-restricted branching programs

Stasys Jukna

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.