DocumentCode
1992473
Title
Space lower-bounds for pseudorandom-generators
Author
Yu, Xiangdong ; Yung, Moti
Author_Institution
Dept. of Comput. Sci., Columbia Univ., New York, NY, USA
fYear
1994
fDate
28 Jun- 1 Jul 1994
Firstpage
186
Lastpage
197
Abstract
Pseudorandom generation is a fundamental notion with many applications such as cryptography and deterministic simulation of random computation. A strong pseudorandom generator w.r.t. a tester class C is one that will “fool” any Turing-test in C to “believe” its output is truly random. We establish the first lower-bounds on the space complexity of general pseudorandom generators (namely, generators with no restrictions on their access to the input seed) which are strong w.r.t the typical time-/space-bounded classes of testers
Keywords
Turing machines; computational complexity; random number generation; Turing machine; Turing-test; cryptography; deterministic simulation; input seed; lower-bounds; pseudorandom-generators; random computation; space complexity; space lower-bounds; tester class; time-space-bounded; Automata; Automatic testing; Computer science; Marine vehicles; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location
Amsterdam
Print_ISBN
0-8186-5670-0
Type
conf
DOI
10.1109/SCT.1994.315805
Filename
315805
Link To Document