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 first demonstrate the approach for read-once b.p. Then we
introduce a strictly larger class of so-called "gentle" b.p. and,
using the suggested approach, prove that some explicit Boolean
functions, including the Clique function and a
particular Pointer function (which belongs to AC^0), cannot be
computed by gentle program of polynomial size. These lower bounds
are new since explicit functions, which are known to be hard for all
previously considered reading-restricted classes of b.p. (such as
(1,+s)-b.p. or syntactic read-k-times b.p.) can be easily
computed by gentle b.p. of polynomial size.