[ACM Press the twenty-fifth annual ACM symposium - San Diego, California, United States (1993.05.16-1993.05.18)] Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 - More deterministic simulation in logspace

✍ Scribed by Nisan, Noam; Zuckerman, David

• Book ID: 120812394
• Publisher: ACM Press
• Year: 1993
• Weight: 807 KB
• Category: Article
• ISBN-13: 9780897915915
• DOI: 10.1145/167088.167162

✦ Synopsis

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 main technical tool: a procedure which extracts randomness from a defective random source using a small additional number of truly random bits. Indeed, from Savitch's proof it follows that a language accepted by a randomized-space(S) machine using R random bits is also accepted by a deterministicspace(S log(R/S)) machine.There is only one result that improves this bound for some R. Namely, Ajtai, Komlos, and Szemeredi showed that any randomizedspace(S) algorithm using only 0(S2 / log S) random