Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-020 | 20th February 2001 00:00

Lower Bounds for OBDDs and Nisan's pseudorandom generator

RSS-Feed




TR01-020
Authors: N. S. Narayanaswamy, C.E. Veni Madhavan
Publication: 7th March 2001 13:06
Downloads: 3528
Keywords: 


Abstract:


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