Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

TR22-093 | 28th June 2022
Joshua Cook

More Verifier Efficient Interactive Protocols For Bounded Space

Revisions: 4

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

ISSN 1433-8092 | Imprint