Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with DLOGTIME-uniformity:
TR04-020 | 8th March 2004
Emanuele Viola

The Complexity of Constructing Pseudorandom Generators from Hard Functions

We study the complexity of building
pseudorandom generators (PRGs) from hard functions.

We show that, starting from a function f : {0,1}^l -> {0,1} that
is mildly hard on average, i.e. every circuit of size 2^Omega(l)
fails to compute f on at least a 1/poly(l)
fraction of inputs, we can ... more >>>

ISSN 1433-8092 | Imprint