Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am reading the classic "Hardness vs Randomness" by Nisan and Wigderson. Let $B=\{0,1\}$, and fix a function $l\colon \mathbb{N} \to \mathbb{N}$. They define a family of functions $G = \{G_n : B^{l(n)} \to B^n\}$ to be pseudorandom in case for every circuit of size $n$ we have

$(*) \ \ | P(C(x) = 1) - P(C(G(y))=1) | < 1/n$

(where $x \in B^{n},y \in B^{l(n)}$ are uniform random variables).

I understand that I am to think of $x$ and $y$ as random variables, and that I want to compare the distance between $x$ and $G(y)$ as random variables. I get the intuition that circuits are being used as sort of "tests" in to see if $G$ can be "figured out." What I am really struggling with is why the condition $(*)$ is the right one. Does anyone have any advice on how to think of this definition?

share|cite|improve this question
Check your spelling of the authors' names... – rphv Nov 14 '12 at 16:16
@rphv fixed it. – Suresh Venkat Nov 14 '12 at 16:22
up vote 21 down vote accepted

There are two aspect that need to be mentioned.

The first is the general idea of defining a PRG by having its output look different than uniform to small circuits. This idea goes back to Yao and is really the strongest possible definition you can ask for when aiming explicitly at pseudo-randomness for computationally-bounded observers.

The second aspect is the choice of parameters where we limit the circuit size to be $n$ and the acceptance probability difference to be $1/n$, where $n$ is also the PRG output size. This choice is somewhat different than the usual crypto one where the circuit size is $poly(n)$ and the probability difference is required to be smaller than any $poly(n)$. In our case specific parameters (rather than $poly(n)$) were needed as to get the tightest results including, in particular polynomial simulations. While in principle one could have 3 different parameters, it turned out that our results had these working essentially in the same way so we folded them to a single one (in addition to the input size $l(n)$ which was viewed as a function of $n$).

share|cite|improve this answer
Thank you Noam for the answer. It was very much helpful. – user12484 Nov 14 '12 at 19:50

I am by no means an expert on this, but a key component of the definition of pseudorandomness (as opposed to attempts to define randomness) is that the goal of something "pseudorandom" is to fool a circuit. In other words, the motivation is to think of the pseudorandom string being supplied to the circuit instead of the truly random string.

In that sense, it's not really that you're trying to pretend that $x$ and $G(y)$ "look the same". It's that they "look the same" to a circuit (of necessarily bounded complexity).

So the role of the circuit is crucial, as opposed to merely being a "test function".

share|cite|improve this answer

Hopefully, I can expand just a little on Suresh's response. First, I don't think that the strictness of the inequality is needed in your $(*)$, and I am also not sure why $1/n$ is needed, and not $1/2n$ or something else. However, practically, I think 1/n is enough to get some interesting theoretical results.

But then you almost certainly want to assert that each $G_i$ is computable in some amount of time, say exponential. Further, I think you will have to assert that $l(n) < n$. You can think of $l(n)$ as the seed length. Thus $G_i$ is pseudorandom if it can increase the number of bits in a random string of length $l(n)$ without being detected by a circuit of size less than $n$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.