Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR05-079 | 25th July 2005 00:00

#### Expanders and time-restricted branching programs

TR05-079
Authors: Stasys Jukna
Publication: 25th July 2005 21:14
Keywords:

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.

ISSN 1433-8092 | Imprint