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