2
$\begingroup$

I'm trying to prove that an inefficient double-lengthening PRG exists, i.e. construct a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$

My current approach is to bound the number of poly-time non-uniform algorithms as the number of boolean circuits, which is $2^{n^2}$, then we can say there $2^{n^2}$ functions, we will call them $F_i, 1 \leq i \leq 2^{n^2}$. Then we will have $2^{2n}$ variables, each $t_{i}, 1 \leq i \leq 2^{2n}$, and we will want to bound the $min ( {max_{1 \leq j \leq 2^{n^2}}} (\sum_{1\leq x \leq2^{2n}} t_x F_j(x)) - \sum_{1\leq x \leq2^{2n}} F_j(x)))$

with the constraints that: $\sum_{1 \leq x \leq 2^{2n}} t_x = 2^n$ and $\forall 1 \leq x \leq 2^{2n}, 0 \leq t_x$

My aim is to show that this minimum is surely negligible, but I don't have a lot of background on constraint equations and I'm not sure if perhaps it's the right approach.

Improve this question
$\endgroup$
1
  • $\begingroup$ The parenthesis in the formula starting in $min$ are not balanced, and (perhaps independently) it's not clear over what the minimum is computed. Also, $\min$ and $\max$ are keywords written \minand \max, Perhaps adding \displaystyle at start of expressions would make them clearer. $\endgroup$
    – fgrieu ♦
    Commented Feb 19 at 20:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.