Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-030 | 9th June 1998 00:00

On Branching Programs With Bounded Uncertainty


Authors: Stasys Jukna, Stanislav Zak
Publication: 9th June 1998 11:50
Downloads: 2197


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.

ISSN 1433-8092 | Imprint