Expanders and time-restricted branching programs |
| |
Authors: | Stasys Jukna |
| |
Affiliation: | Institute of Mathematics and Computer Science, Akademijos 4, Vilnius, Lithuania |
| |
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; the sets of variables re-tested along different computations may be different. For every branching program, this number lies between 0 (read-once programs) and the total number n of variables (general branching programs). The best results so far were exponential lower bounds on the size of branching programs with R=o(n/logn). We improve this to R≤?n for a constant ?>0. This also gives an alternative and simpler proof of an exponential lower bound for (1+?)n time branching programs for a constant ?>0. We prove these lower bounds for quadratic functions of Ramanujan graphs. |
| |
Keywords: | Computational complexity Branching programs Lower bounds Expander graphs Ramanujan graphs |
本文献已被 ScienceDirect 等数据库收录! |