Randomness is Linear in Space
Journal of Computer and System SciencesPublished 1 February 1996
Noam Nisan, David Zuckerman
Citations652
SJR quartileQ1
SJR score1.03
SNIP1.08
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Of independent interest is the main technical tool: a procedure which extracts randomness from a defective random source using a small additional number of truly random bits.
Abstract
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 deterministic simulation in spaceSfollows. Of independent interest is our main technical tool: a procedure which extracts randomness from a defective random source using a small additional number of truly random bits.
Keywords
Computer ScienceMathematics
Journal of Computer and System SciencesUniversal classes of hash functions
2,573 Citations1979J.Lawrence Carter, Mark N. Wegman
An input independent average linear time algorithm for storage and retrieval on keys that makes a random choice of hash function from a suitable class of hash functions.
Journal of Computer and System SciencesRelationships between nondeterministic and deterministic tape complexities
1,362 Citations1970Walter J. Savitch
The amount of storage needed to simulate a nondeterministic tape bounded Turingmachine on a deterministic Turing machine is investigated and a specific set is produced, namely the set of all codings of threadable mazes, such that, if there is any set which distinguishes nondeter microscopic complexity classes from deterministic tape complexity classes, then this is one such set.
SIAM Journal on ComputingApproximating the Permanent
793 Citations1989Mark Jerrum, Alistair Sinclair
A randomised approximation scheme for the permanent of a 0–1s presented, demonstrating that the matchings chain is rapidly mixing, apparently the first such result for a Markov chain with genuinely c...
Pseudo-random generation from one-way functions
710 Citations1989Russell Impagliazzo, Leonid A. Levin +1 more
From one-way functions of type (1) or (2) it is shown how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa.
SIAM Journal on ComputingUnbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
554 Citations1988Benny Chor, Oded Goldreich
COMBINATORICAPseudorandom generators for space-bounded computation
420 Citations1992Noam Nisan
Pseudorandom generators are constructed which convertO(SlogR) truly random bits toR bits that appear random to any algorithm that runs inSPACE(S) that can be simulated using onlyO(Slogn) random bits.
How to recycle random bits
396 Citations1989Russell Impagliazzo, David Zuckerman
It is shown that modified versions of the linear congruential generator and the shift register generator are provably good for amplifying the correctness of a probabilistic algorithm.
Journal of Computer and System SciencesMultiparty protocols, pseudorandom generators for logspace, and time-space trade-offs
257 Citations1992László Babai, Noam Nisant +1 more
Lower bounds of the form Ω(n · c−k), for the number of bits that need to be exchanged in order to compute some (explicitly given) polynomial time computable functions are proved.
Deterministic simulation in LOGSPACE
204 Citations1987Miklós Ajtai, János Komlós +1 more
It is shown that a wide class of probabilistic algorithms can be simulated by deterministic algorithms, and if there is a test in LOGSPACE so that a random sequence of length (log n)2 / log log n passes the test with probability at least 1/n then a deterministic sequence can be constructed inLOGSPACE which also passed the test.
Journal of Computer and System SciencesRemoving randomness in parallel computation without a processor penalty
194 Citations1993Michael Luby
Journal of ComplexityOn the power of two-point based sampling
194 Citations1989Benny Chor, Oded Goldreich
A new sampling technique is presented that consists of picking two elements at random, and deterministically generating a long sequence of pairwise-independent elements that is guaranteed to intersect, with high probability, any set of non-negligible density.
Dispersers, deterministic amplification, and weak random sources
184 Citations1989Aviad Cohen, Avi Wigderson
The use of highly expanding bipartite multigraphs (called dispersers) to reduce greatly the error of probabilistic algorithms at the cost of few additional random bits is treated.
AlgorithmicaSimulating BPP using a general weak random source
143 Citations1996David Zuckerman
This work shows how to simulate BPP and approximation algorithms in polynomial time using the output from a δ-source, and gives an application to the unapproximability of MAX CLIQUE.
General weak random sources
104 Citations2002David Zuckerman
Under the generalized Paley graph conjecture, a generator that runs in polynomial time and simulates RP is given, as well as a different generator that produces almost perfectly random bits at a rate arbitrarily close to optimal using as seeds strings from a constant number of independent weak random sources.
Journal of Computer and System SciencesThe probabilistic method yields deterministic parallel algorithms
102 Citations1994Rajeev Motwani, Joseph Naor +1 more
Journal of the ACMSimulating (log <sup>c</sup> <i>n</i> )-wise independence in NC
88 Citations1991Bonnie Berger, John Rompel
A general framework for removing randomness from randomized NC algorithms whose analysis uses only polyalgorithmic independence is developed, which can be used to obtain many other NC algorithms, including a better NC edge coloring algorithm.
Computational ComplexityRandomness in interactive proofs
57 Citations1993Mihir Bellare, Oded Goldreich +1 more
This paper shows how to construct an AM proof system forL which, in the same number of rounds as the original proof system, achieves error 2−k(n) at the cost of Arthur sending onlyO(l) random bits per round.
Symposium on Discrete AlgorithmsChernoff-Hoeffding bounds for applications with limited independence
48 Citations1993Jeanette P. Schmidt, Alan Siegel +1 more