Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-057 | 25th July 2000 00:00

An Improved Hierarchy Result for Partitioned BDDs


Authors: Martin Sauerhoff
Publication: 2nd August 2000 10:02
Downloads: 3025


One of the great challenges of complexity theory is the problem of
analyzing the dependence of the complexity of Boolean functions on the
resources nondeterminism and randomness. So far, this problem could be
solved only for very few models of computation. For so-called
partitioned binary decision diagrams, which are a restricted variant of
nondeterministic read-once branching programs, Bollig and Wegener have
proven an astonishing hierarchy result which shows that the smallest
possible decrease of the available amount of nondeterminism may incur
an exponential blow-up of the branching program size.

They have shown that k-partitioned BDDs which may nondeterministically
choose between k alternative subprograms may be exponentially larger
than (k+1)-partitioned BDDs for the same function if
k = o((log n/loglog n)^{1/2}), where n is the input size.
In this paper, an improved hierarchy result is established which still
works if the number of nondeterministic decisions is
O((n/log^{1+c} n)^{1/4}), where c > 0 is an arbitrary small constant.

ISSN 1433-8092 | Imprint