$$

Suppose we want to fool a complexity class $\mathcal{C}$. That is, we want to find an explicit function $g:{\{0,1\}}^r\to {\{0,1\}}^n$ that blows up a small $r$-bit “seed” into a long $n$-bit string in such a way that the output “fools” any functions in $\mathcal{C}$. That is, the “sample mean” (over the $2^r$ output values of $g$) should closely match the “true mean”:

$$\underset{s\in {\{0,1\}}^r}{\mathrm{Pr}}[f(g(s))]\in \underset{x\in {\{0,1\}}^n}{\mathrm{Pr}}[f(x)]\pm ϵ.$$

How big does $r$ need to be as a function of $\mathcal{C}$?

The gold standard for a pseudorandom generator would be to match the performance of a randomly chosen sample of $2^r$ strings from ${\{0,1\}}^n$.

By a Hoeffding bound, for any given $f\in \mathcal{C}$, the chance that the sample mean for $f$ is off by more than $ϵ$ is $\le 2^{-\mathrm{\Omega }(2^r{ϵ}^2)}$. So to make sure that this sample works for all functions in some class $\mathcal{C}$ simultaneously, we set (roughly)

$$\underset{\text{failure probability}}{\underbrace{2^{-2^r{ϵ}^2}=1/|\mathcal{C}|}}\iff \underset{\text{sample size}}{\underbrace{2^r=(\log |C|)/{ϵ}^2}}\iff \underset{\text{seed length}}{\underbrace{r=\mathrm{\Theta }(\log \log |\mathcal{C}|+\log (1/ϵ))}}.$$