Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-020 | 20th February 2001 00:00

Lower Bounds for OBDDs and Nisan's pseudorandom generator


Authors: N. S. Narayanaswamy, C.E. Veni Madhavan
Publication: 7th March 2001 13:06
Downloads: 1320


We present a new boolean function for which any Ordered Binary
Decision Diagram (OBDD) computing it has an exponential number
of nodes. This boolean function is obtained from Nisan's
pseudorandom generator to derandomize space bounded randomized
algorithms. Though the relation between hardness and randomness for
computational models is well known, to the best of our knowledge,
this is the first study relating the problem of proving lower bounds
for OBDDs to the issue of pseudorandom generators for space bounded
computation. Using the same technique to prove the OBDD size lower
bound, we place a lower
bound on the size of
families of hash functions used in Nisan's pseudorandom generator.
This lower bound rules out one method of obtaining improved
derandomizations of space bounded randomized algorithms.

ISSN 1433-8092 | Imprint