Name
Abstract | ||
|---|---|---|
(MATH) We construct the first pseudo-random generators with logarithmic seed length that convert s bits of hardness into sΩ(1) bits of 2-sided pseudo-randomness for any s}. This improves [8] and gives a direct proof of the optimal hardness vs. randomness tradeoff in [15]. A key element in our construction is an augmentation of the standard low-degree extension encoding that exploits the field structure of the underlying space in a new way. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0022-0000(03)00046-1 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
complexity classes,complexity class,pseudo random generator,circuit complexity,pseudo random number generator | Conference | 67 |
Issue | ISSN | ISBN |
2 | Journal of Computer and System Sciences | 1-58113-495-9 |
Citations | PageRank | References |
49 | 1.61 | 22 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christopher Umans | 1 | 879 | 55.36 |