Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-101 | 14th December 2001 00:00

A Lower Bound Technique for Restricted Branching Programs and Applications


Authors: Philipp Woelfel
Publication: 17th December 2001 20:33
Downloads: 4259


We present a new lower bound technique for two types of restricted
Branching Programs (BPs), namely for read-once BPs (BP1s) with
restricted amount of nondeterminism and for (1,+k)-BPs. For this
technique, we introduce the notion of (strictly) k-wise l-mixed
Boolean functions, which generalizes the concept of l-mixedness
defined by Jukna in 1988. We prove that if a Boolean function f is
(strictly) k-wise l-mixed, then any nondeterministic BP1 with at most
k-1 nondeterministic nodes and any (1,+k)-BP representing f has a
size of at least 2^Omega(l). While leading to new exponential lower
bounds of well-studied functions (e.g. linear codes), the lower bound
technique also shows that the polynomial size hierarchy for BP1s with
respect to the available amount of nondeterminism is strict. More
precisely, we present a class of functions which can be represented
by polynomial size BP1s with k nondeterministic nodes, but require
superpolynomial size if only k-1 nondeterministic nodes are available
( for k=o(n^(1/3)/(log n)^(2/3)) ). This is the first hierarchy result
of this kind where the BP1 does not obey any further restrictions. We
also obtain a hierarchy result with respect to k for (1,+k)-BPs as
long as k=o((n/log n)^(1/2)). This extends the hierarchy result of
Savicky and Zak (2000), where k was bounded above by
(1/2)n^(1/6)/(log n)^(1/3).

ISSN 1433-8092 | Imprint