Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANDOMIZED SPACE BOUNDED ALGORITHMS:
Reports tagged with randomized space bounded algorithms:
TR01-020 | 20th February 2001
N. S. Narayanaswamy, C.E. Veni Madhavan

Lower Bounds for OBDDs and Nisan's pseudorandom generator


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 ... more >>>




ISSN 1433-8092 | Imprint