Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

On the Derandomization of Space-Bounded Computations

Roy ArmoniContact Information

(7)  Institute of Computer Science, The Hebrew University of Jerusalem, Israel
Abstract
We construct a pseudo-random generator for space bounded computations using the extractor of Zuckerman [7]. For machines that use S space and R < 2 1-ε random bits for ε Τ; 0, the generator uses a seed of length O((S log R)/ log S) which is shorter than the seed of both the generator of Nisan [4] and the generator of Nisan and Zuckerman[5]. We then use this generator to derandomize these machines in space $$
O(S\sqrt {(\log R)/\log S} )$$ which is better than the derandomization of [6].

Contact Information Roy Armoni
Email: aroy@cs.huji.ac.il
URL: http://www.cs.huji.ac.il/~aroy
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb07
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)