Expanders and time-restricted branching programs

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 / log n ). 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.

Authors

• Stasys Jukna

Keywords

• Computational complexity
• Branching programs
• Lower bounds
• Expander graphs
• Ramanujan graphs