RANDOMNESS IS LINEAR IN-SPACE

Authors
NISAN N ZUCKERMAN D
Citation
N. Nisan et D. Zuckerman, RANDOMNESS IS LINEAR IN-SPACE, Journal of computer and system sciences, 52(1), 1996, pp. 43-52
Citations number
21
Categorie Soggetti
System Science","Computer Science Hardware & Architecture","Computer Science Theory & Methods
Journal title
Journal of computer and system sciences → ACNP
ISSN journal
00220000
Volume
52
Issue
1
Year of publication
1996
Pages
43 - 52
Database
ISI
SICI code
0022-0000(1996)52:1<43:RILI>2.0.ZU;2-A
Abstract
We show that any randomized algorithm that runs in space S and time T and uses poly(S) random bits can be simulated using only O(S) random b its in space Sand time T+poly(S). A deterministic simulation in space S follows. Of independent interest is our main technical tool: a proce dure which extracts randomness from a defective random source using a small additional number of truly random bits. (C) 1996 Academic Press. Inc.