Pseudorandom generators are constructed which convert O (SlogR) truly random bits to R
bits that appear random to any algorithm that runs in SPACE (S). In particular, any …

Let M be a logarithmic space Turing machine (or a polynomial width branching pmgram) that
USES up to kzp/G (read once) random bits. For a fixed input, let E (S) be the probability (over …

We show that any randomized algorithm that runs in spaceSand timeTand uses poly (S)
random bits can be simulated using onlyO (S) random bits in spaceSand timeT+ poly (S). A …

We show that any randomized space (S) algorithm which uses only poly (S) random bits can
be simulated deterministically in space (S), for S (n)~ log n. Of independent interest is our …

For every integer d we explicitly construct a family of functions (pseudo-random bit
generators) that convert a polylogarithmic number of truly random bits to n bits that appear …

We present a simple new construction of a pseudorandom bit generator. It stretches a short
string of truly random bits into a long string that looks random to any algorithm from a …

One-way are those functions which are easy to compute, but hard to invert on a non-
negligible fraction of instances. The existence of such functions with some additional …

This is a survey of pseudorandomness, the theory of efficiently generating objects that" look
random" despite being constructed using little or no randomness. This theory has …

Random Polynomial Time (Rp) is currently considered to be the class of tractable
computational problems. Here one assumes a source of truly random bits. However, the …

We prove that given a function f which is oneway in the uniform model (ie cannot be inverted
except on a vanishing fraction of the inputs by a probabilistic polynomial time Turing …