ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-079 | 25th July 2005 00:00

Expanders and time-restricted branching programs

RSS-Feed




TR05-079
Authors: Stasys Jukna
Publication: 25th July 2005 21:14
Downloads: 606
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