Suppose we have a length-increasing function , which we think of as a pseudorandom generator mapping a shorter seed into a longer output.
Then the distribution of for a random seed is not uniform (in particular, it is concentrated on at most of the elements of ). We say that a statistical test has advantage in distinguishing the output of from the uniform distribution if
If the left-hand side of (1) is at most for every computable by a circuit of size , then we say that is -pseudorandom against circuits of size , or that it is an -secure pseudorandom generator.
How secure can a pseudorandom generator possibly be? This question (if we make no assumption on the efficiency of ) is related to the question in the previous post on approximating a boolean function via small circuits. Both questions, in fact, are special cases of the question of how much an arbitrary real-valued function must correlate with functions computed by small circuits, which is answered in a new paper with Anindya De and Madhur Tulsiani.