ECCC-Report TR01-039https://eccc.weizmann.ac.il/report/2001/039Comments and Revisions published for TR01-039en-usMon, 04 Mar 2002 00:00:00 +0200
Revision 1
| On Uncertainty versus Size in Branching Programs |
Stasys Jukna,
Stanislav Zak
https://eccc.weizmann.ac.il/report/2001/039#revision1Mon, 04 Mar 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2001/039#revision1
Paper TR01-039
| On Uncertainty versus Size in Branching Programs |
Stasys Jukna,
Stanislav Zak
https://eccc.weizmann.ac.il/report/2001/039We 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.
Fri, 18 May 2001 14:26:41 +0300https://eccc.weizmann.ac.il/report/2001/039