N. S. Narayanaswamy, C.E. Veni Madhavan

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

Joshua Cook

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$, and $\mathbf{CoNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$. ... more >>>