<p>In these <a href="http://www.wisdom.weizmann.ac.il/~gilc/talks/CTS14.ppsx" rel="nofollow">slides</a>, it is mentioned that for a class of functions $\mathcal{C}$, a pseudorandom generator is a distribution $D$ such that</p>

<ol>
<li>$D$ fools $\mathcal{C}$.</li>
<li>$D$ is efficiently samplable.</li>
<li>$D$ is sampled using a few random bits.</li>
</ol>

<p>Then if you want to achieve $(1)$ and $(2)$, let $D = U$, where $U$ is the uniform distribution. This is clear to me. It's mentioned further that for $(1)$ and $(3)$: $\forall \mathcal{C}$ $\exists$ inefficiently samplable $D$ using $O(\log \log |\mathcal{C}|)$ random bits. Could someone explain how to construct such an inefficient $D$?</p>

CC BY-SA 3.0
2015-06-17T16:21:56.267Z
Use the probabilistic method. A random function is a PRG with high probability.
Or Meir
CC BY-SA 3.0
2015-06-17T16:39:16.750Z
Why $O(\log \log |\mathcal{C}|)$ random bits needed in this case?
user34478
CC BY-SA 3.0
2015-06-17T19:48:25.643Z
Try to do the calculation.
Or Meir
CC BY-SA 3.0
2015-06-17T19:51:48.777Z
You have log|C| random elements in your distribution. How many bits do you need to choose one of them at random?
Kaveh
CC BY-SA 3.0
2015-06-17T20:10:53.743Z
@Kaveh But $\mathcal{C}$ is the class of functions to be fooled. How can this be related to the number of random functions to choose from, which should fool all $f \in \mathcal{C}$? That is, first we fix a distribution $D$, then the promise is it should fool $\mathcal{C}$, meaning this should be oblivious to the size of $\mathcal{C}$.
user34478
CC BY-SA 3.0
2015-06-17T22:08:05.947Z
I think working out a concrete example would help. Look at slide 7 and work out the details on how the probabilistic construction works for fooling n linear functions. Also think about the number of bits for the D=U case.
Kaveh
<pseudorandom-generators>
Inefficient pseudorandom distribution using a few random bits
user34478
# Inefficient pseudorandom distribution using a few random bits

(Asked by: username_0 on 2015-06-17)

In these [slides](http://www.wisdom.weizmann.ac.il/~gilc/talks/CTS14.ppsx), it is mentioned that for a class of functions $\mathcal{C}$, a pseudorandom generator is a distribution $D$ such that

1. $D$ fools $\mathcal{C}$.
2. $D$ is efficiently samplable.
3. $D$ is sampled using a few random bits.

Then if you want to achieve $(1)$ and $(2)$, let $D = U$, where $U$ is the uniform distribution. This is clear to me. It's mentioned further that for $(1)$ and $(3)$: $\forall \mathcal{C}$ $\exists$ inefficiently samplable $D$ using $O(\log \log |\mathcal{C}|)$ random bits. Could someone explain how to construct such an inefficient $D$?

**Tags:** pseudorandom-generators
> **Comments:**
> **username_1**: Use the probabilistic method. A random function is a PRG with high probability.  
> **username_0**: Why $O(\log \log |\mathcal{C}|)$ random bits needed in this case?  
> **username_1**: Try to do the calculation.  
> **username_2**: You have log|C| random elements in your distribution. How many bits do you need to choose one of them at random?  
> **username_0**: @Kaveh But $\mathcal{C}$ is the class of functions to be fooled. How can this be related to the number of random functions to choose from, which should fool all $f \in \mathcal{C}$? That is, first we fix a distribution $D$, then the promise is it should fool $\mathcal{C}$, meaning this should be oblivious to the size of $\mathcal{C}$.  
> **username_2**: I think working out a concrete example would help. Look at slide 7 and work out the details on how the probabilistic construction works for fooling n linear functions. Also think about the number of bits for the D=U case.  

---

## 0 answers

