ECCC-Report TR05-079https://eccc.weizmann.ac.il/report/2005/079Comments and Revisions published for TR05-079en-usMon, 25 Jul 2005 21:14:37 +0300
Paper TR05-079
| Expanders and time-restricted branching programs |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2005/079 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.
Mon, 25 Jul 2005 21:14:37 +0300https://eccc.weizmann.ac.il/report/2005/079