ECCC-Report TR95-002https://eccc.weizmann.ac.il/report/1995/002Comments and Revisions published for TR95-002en-usSun, 01 Jan 1995 00:00:00 +0200
Paper TR95-002
| New Lower Bounds and Hierarchy Results for Restricted Branching Programs |
Detlef Sieling
https://eccc.weizmann.ac.il/report/1995/002In 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.
Sun, 01 Jan 1995 00:00:00 +0200https://eccc.weizmann.ac.il/report/1995/002