ECCC-Report TR12-057https://eccc.weizmann.ac.il/report/2012/057Comments and Revisions published for TR12-057en-usWed, 26 Sep 2012 03:37:57 +0200
Revision 2
| Pseudorandomness from Shrinkage |
Russell Impagliazzo,
Raghu Meka,
David Zuckerman
https://eccc.weizmann.ac.il/report/2012/057#revision2One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models where we only know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can indeed construct PRGs which are essentially best possible without in turn improving the lower bounds.
More specifically, say that a circuit family has shrinkage exponent Gamma if a random restriction leaving a p fraction of variables unset shrinks the size of any circuit in the family by a factor of $p^{\Gamma}$. Our PRG uses a seed of length roughly $s^{1/(\Gamma + 1)}$ to fool circuits in the family of size $s$. By instantiating this generic construction, we get PRGs for the following classes:
1) de Morgan formulas of size $s$, seed length $s^{1/3+o(1)}$.
2) Formulas over an arbitrary basis of size $s$, seed length $s^{1/2+o(1)}$.
3) Read-once formulas, seed length $s^{.234...}$.
4) Branching programs of size $s$, seed length $s^{1/2 + o(1)}$.
The previous best PRGs known for these classes used seeds of length bigger than $n/2$ to output $n$ bits, and worked only when the size $s=O(n)$.Wed, 26 Sep 2012 03:37:57 +0200https://eccc.weizmann.ac.il/report/2012/057#revision2
Revision 1
| Pseudorandomness from Shrinkage |
Russell Impagliazzo,
Raghu Meka,
David Zuckerman
https://eccc.weizmann.ac.il/report/2012/057#revision1One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models where we only know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can indeed construct PRGs which are essentially best possible without in turn improving the lower bounds.
More specifically, say that a circuit family has shrinkage exponent Gamma if a random restriction leaving a p fraction of variables unset shrinks the size of any circuit in the family by a factor of $p^{\Gamma}$. Our PRG uses a seed of length roughly $s^{1/(\Gamma + 1)}$ to fool circuits in the family of size $s$. By instantiating this generic construction, we get PRGs for the following classes:
1) de Morgan formulas of size $s$, seed length $s^{1/3+o(1)}$.
2) Formulas over an arbitrary basis of size $s$, seed length $s^{1/2+o(1)}$.
3) Read-once formulas, seed length $s^{.234...}$.
4) Branching programs of size $s$, seed length $s^{1/2 + o(1)}$.
The previous best PRGs known for these classes used seeds of length bigger than $n/2$ to output $n$ bits, and worked only when the size $s=O(n)$.Tue, 22 May 2012 02:47:46 +0300https://eccc.weizmann.ac.il/report/2012/057#revision1
Paper TR12-057
| Pseudorandomness from Shrinkage |
Russell Impagliazzo,
Raghu Meka,
David Zuckerman
https://eccc.weizmann.ac.il/report/2012/057One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models where we only know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can indeed construct PRGs which are essentially best possible without in turn improving the lower bounds.
More specifically, say that a circuit family has shrinkage exponent Gamma if a random restriction leaving a p fraction of variables unset shrinks the size of any circuit in the family by a factor of $p^{\Gamma}$. Our PRG uses a seed of length roughly $s^{1/(\Gamma + 1)}$ to fool circuits in the family of size $s$. By instantiating this generic construction, we get PRGs for the following classes:
1) de Morgan formulas of size $s$, seed length $s^{1/3+o(1)}$.
2) Formulas over an arbitrary basis of size $s$, seed length $s^{1/2+o(1)}$.
3) Read-once formulas, seed length $s^{.234...}$.
4) Branching programs of size $s$, seed length $s^{1/2 + o(1)}$.
The previous best PRGs known for these classes used seeds of length bigger than $n/2$ to output $n$ bits, and worked only when the size $s=O(n)$.Mon, 07 May 2012 18:00:17 +0300https://eccc.weizmann.ac.il/report/2012/057