Definition
Let Fn = {f: {0, 1}n → T} be a class of functions. A function G: {0, 1}s → {0, 1}n, where s < n, is a pseudorandom generator against Fn with bias ε if for every f in Fn, the statistical distance between the distributions f(G(X)), where X is sampled from the uniform distribution on {0, 1}s, and f(Y), where Y is sampled from the uniform distribution on {0, 1}n, is at most ε.
The quantity s is called the seed length and the quantity n - s is called the stretch of the pseudorandom generator. Functions from the class Fn are sometimes called adversaries.
A pseudorandom generator against a family of adversaries F = {Fn} with bias ε(n) is a collection of pseudorandom generators {Gn: {0, 1}s(n) → {0, 1}n}, where Gn is a pseudorandom generator against Fn with bias ε(n).
In most applications, the family F represents some model of computation, and one is interested in desigining a pseudorandom generator that is computable in the same or some closely related model.
Read more about this topic: Pseudorandom Generator
Famous quotes containing the word definition:
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)
“Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
—Walter Pater (1839–1894)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)