__
TR95-002 | 1st January 1995 00:00
__

#### New Lower Bounds and Hierarchy Results for Restricted Branching Programs

**Abstract:**
In unrestricted branching programs all variables may be tested

arbitrarily often on each path. But exponential lower bounds are only

known, if on each path the number of tests of each variable is bounded

(Borodin, Razborov and Smolensky (1993)). We examine branching programs

in which for each path the number of variables that are tested more than once

is bounded by $k$, but we do not bound the number of tests of those

variables. A new lower bound method admits to prove that we can

enhance the expressive power of such branching programs by

increasing $k$ only by $1$: For

$k\leq(1-\varepsilon)(n/3)^{1/3}/\log^{2/3}n$, where

$\varepsilon > 0$, we exhibit Boolean functions that can be

represented in polynomial size, if $k$ variables may be tested

more than once on each path, but only in exponential

size, if $(k-1)$ variables may be tested more than once on each path.

Therefore, we obtain a tight hierarchy.