ECCC-Report TR18-133https://eccc.weizmann.ac.il/report/2018/133Comments and Revisions published for TR18-133en-usMon, 11 Mar 2019 03:21:18 +0200
Revision 1
| Constant-error pseudorandomness proofs from hardness require majority |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/133#revision1Research 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.
Mon, 11 Mar 2019 03:21:18 +0200https://eccc.weizmann.ac.il/report/2018/133#revision1
Paper TR18-133
| Constant-error pseudorandomness proofs from hardness require majority |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/133Research 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.
Thu, 26 Jul 2018 20:10:00 +0300https://eccc.weizmann.ac.il/report/2018/133