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
depth of so-caled `splitting trees' for sets of inputs reaching
particular nodes of the program.
<P>

We first demonstrate the approach for
read-once branching programs. Then we introduce a strictly larger
class of so-called `balanced' branching programs and, using the
suggested approach, prove that some explicit Boolean functions
cannot be computed by balanced programs of polynomial size.
These lower bounds are new since some explicit functions, which
are known to be hard for most previously considered restricted classes
of branching programs, can be easily computed by balanced branching
programs of polynomial size.
<P>

This is a substantially simplified and conceptually different
version of ECCC TR98-030.