Title :
Space lower-bounds for pseudorandom-generators
Author :
Yu, Xiangdong ; Yung, Moti
Author_Institution :
Dept. of Comput. Sci., Columbia Univ., New York, NY, USA
fDate :
28 Jun- 1 Jul 1994
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;
Conference_Titel :
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location :
Amsterdam
Print_ISBN :
0-8186-5670-0
DOI :
10.1109/SCT.1994.315805
