We propose an information-theoretic approach to proving lower
bounds on the size of branching programs. The argument is based on
Kraft-McMillan type inequalities for the average amount of
uncertainty about (or entropy of) a given input during the various
stages of computation. The uncertainty is measured by the average
more >>>

We propose an information-theoretic approach to proving
lower bounds on the size of branching programs (b.p.). The argument
is based on Kraft-McMillan type inequalities for the average amount of
uncertainty about (or entropy of) a given input during various
stages of the computation.

We ... more >>>

Branching programs (b.p.s) or binary decision diagrams are a
general graph-based model of sequential computation. The b.p.s of
polynomial size are a nonuniform counterpart of LOG. Lower bounds
for different kinds of restricted b.p.s are intensively
investigated. The restrictions based on the number of tests of
more >>>

Branching programs (b.p.'s) or decision diagrams are a general
graph-based model of sequential computation. The b.p.'s of
polynomial size are a nonuniform counterpart of LOG. Lower bounds
for different kinds of restricted b.p.'s are intensively
investigated. An important restriction are so called $k$-b.p.'s,
where each computation reads each input ... more >>>

Branching programs (b.p.'s) or decision diagrams are a general
graph-based model of sequential computation. B.p.'s of polynomial
size are a nonuniform counterpart of LOG. Lower bounds for
different kinds of restricted b.p.'s are intensively investigated.
An important restriction are so called 1-b.p.'s, where each
computation reads each input bit at ... more >>>