Timeline for Connection between Pseudo random generators and hardness
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 13, 2020 at 5:07 | vote | accept | roydiptajit | ||
| Nov 13, 2020 at 5:07 | vote | accept | roydiptajit | ||
| Nov 13, 2020 at 5:07 | |||||
| Nov 13, 2020 at 2:44 | answer | added | xskxzr | timeline score: 1 | |
| Nov 12, 2020 at 17:04 | history | edited | roydiptajit | CC BY-SA 4.0 |
added 38 characters in body
|
| Nov 12, 2020 at 16:59 | comment | added | roydiptajit | Yes, by $S(l)-prg$, I mean $(S(l),\epsilon)-prg$. Yes, you are right about $G$. I have updated the question to remove $n$ from definition. Sorry for the inconvinience. | |
| Nov 12, 2020 at 10:29 | comment | added | xskxzr | But what is $\epsilon$? Is it a constant, a negligible function of $n$, or a parameter of the definition (i.e., you mean $(S(l),\epsilon)$-Prg rather than $S(l)$-Prg)? In addition, what do you mean by $x\in G$? Do you mean $\mathrm{Pr}_{x\in U_{S^{-1}(n)}}[C_n(G(x))=1]$? You use both $n$ and $l$ in the definition of $S(l)$-Prg, what is the relation between $n$ and $l$? | |
| Nov 12, 2020 at 5:51 | comment | added | roydiptajit | $\epsilon\in(0,\frac{1}{2})$ | |
| Nov 12, 2020 at 3:35 | comment | added | xskxzr | What is $\epsilon$? | |
| Nov 12, 2020 at 3:32 | history | edited | xskxzr | CC BY-SA 4.0 |
edited body
|
| Nov 11, 2020 at 15:53 | comment | added | roydiptajit | I cannot give you the details of the paper, I am sorry, as I did not go through it. All this I got from my university lecture materials. I just want to know if $\exists\;f$, s.t. $S(l)-prg->H_{avg}(f)\geq S((n)$. Definitions are all according to above, might be confusing, that is why I am also struggling with it. What I think is it does not have any connection with NW 1988. | |
| Nov 11, 2020 at 15:02 | history | edited | xskxzr | CC BY-SA 4.0 |
deleted 13 characters in body
|
| Nov 11, 2020 at 14:58 | comment | added | xskxzr | And Theorem 1 in [Nisan Wigderson 1988] states that the two parts are equivalent. Is that what you want? | |
| Nov 11, 2020 at 14:57 | comment | added | xskxzr | You seem to refer to Theorem 1 in [Nisan Wigderson 1988], but the original theorem does not mention 0.01. Where is the 0.01 comes from? | |
| Nov 11, 2020 at 14:06 | comment | added | roydiptajit | " For any general $S(l)$, a Pseudo-random generator, is called an $S(l)-Prg$ if for circuit family $C_n$ of size $S(l)$ $|Pr_{x\in G}[C_n(x)=1]-Pr_{x\in U_n}[C_n(x)=1]|<\epsilon$. Here $G$ is a pseudo random function $G:\{0,1\}^l\longrightarrow\{0,1\}^{S(l)}$, generates an $S(l)$ length strings from length $l$." - This is what I know about $S(l)-prg$. There was a result like this in NIsan Wigderson 1988, but what I asked over here is independent of that. It comes from the definitions and some probability trick, I think.. | |
| Nov 11, 2020 at 11:05 | history | edited | xskxzr |
edited tags
|
|
| Nov 11, 2020 at 11:02 | comment | added | xskxzr | What is $S'(l)Prg$? Which theorem or lemma in [Nisan Wigderson 1988] implies "if there exists $f\in E$ with $H_{avg}(f)\ge S(n)$ then there is a $S'(l)Prg$ where $S'(l)=S(n)^{0.01}$"? | |
| Nov 10, 2020 at 10:54 | history | edited | roydiptajit | CC BY-SA 4.0 |
added 218 characters in body
|
| Nov 9, 2020 at 19:01 | history | edited | roydiptajit | CC BY-SA 4.0 |
added 158 characters in body
|
| Nov 9, 2020 at 16:49 | history | asked | roydiptajit | CC BY-SA 4.0 |