Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-133 | 26th July 2018 20:09

Constant-error pseudorandomness proofs from hardness require majority

RSS-Feed




TR18-133
Authors: Emanuele Viola
Publication: 26th July 2018 20:10
Downloads: 179
Keywords: 


Abstract:

Research in the 80's and 90's showed how to construct a pseudorandom
generator from a function that is hard to compute on more than $99\%$
of the inputs. A more recent line of works showed however that if
the generator has small error, then the proof of correctness cannot
be implemented in subclasses of TC$^{0}$, and hence the construction
cannot be applied to the known hardness results. This paper considers
a typical class of pseudorandom generator constructions, and proves
an analogous result for the case of large error.



ISSN 1433-8092 | Imprint