Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR01-039 | 4th March 2002 00:00

On Uncertainty versus Size in Branching Programs


Revision #1
Authors: Stasys Jukna, Stanislav Zak
Accepted on: 4th March 2002 00:00
Downloads: 3414



TR01-039 | 18th May 2001 00:00

On Uncertainty versus Size in Branching Programs

Authors: Stasys Jukna, Stanislav Zak
Publication: 18th May 2001 14:26
Downloads: 1864


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.

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.

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

ISSN 1433-8092 | Imprint